I do live (fort greene) and work (manhattan) in NYC. You should never use broker's though, they're a waste of money. It does take a little work to find a good deal, but you definitely can if you look early enough.
Overall, I would agree. NJ seems to have the most cheap places.
Great point about 45 commute just inside Manhattan.
EDIT: I live in fort greene and I pay 735 a month -- for validation purposes.