There's an area of about 6 city blocks bordered by Columbia University on the south, 125th St. on the north, Broadway to the east, and Grant's Tomb on the west...and rent is ridiculously cheap! 2BR for $2700 or less (we're paying much less) are not unusual. The 125th St. 1 train stop is right there. I can be in Union Sq. in about 20 min during rush hour, and I can walk to Columbia and most of the UWS. On top of that, if you head to 125th St. and walk toward the water, you've got Dinosaur BBQ and a giant Fairway right there. If you're the biking type, you can go from there straight down the West-side Greenway. Add to all this the fact that Columbia is building their new campus just across 125th St., and you have a little slice of heaven.
Now, most people look at a map and immediately say, "But you're in Harlem!" Well, technically Harlem starts just north of my bedroom window, but yeah...so what? New York is a bit of a peculiar place. I used to live further north in Harlem, and there were literally patches of no more than 4 blocks square where life was perfect, and I never felt I was in any danger. Go another 2 blocks north, though, and you started to feel like you had to watch your back.
If you are going to move to New York, your best bet is to talk to someone who knows New York (hint: if they've lived in New York for less than 5 years, they probably don't know New York).
Anywhere that's a discrete suburb (preferably cut off from where decent people live by a bridge or railway crossing) takes a long time to go from "slum" to "trendy" in the eyes of most people, despite it actually being a nice place to live. But everyone who is in on the secret gets outrageously cheap rent, a great place to buy, and funny looks from co-workers.
Another tip for prospective New Yorkers: find out where filming permits are being issued. Film crews will stay away from the overly expensive (stuck-up-ish, NIMBY-ish) neighborhoods, but they also won't go anywhere overly risky. As a nice added bonus, typically the area will be picturesque (though not always).
For example: "Person of Interest" was filming in front of our building on Monday, episodes of "Blue Bloods" and "Gossip Girl" have filmed within a couple blocks, and the outdoor scenes at the end of Lady Gaga's video for "Marry the Night" were shot right by the Fairway 3 blocks away.
So talk to me. I grew up and live here. And your best bet is actually NJ. Hoboken or Jersey City. They're on the PATH. Your commute to Manhattan will be 15 minutes and a ticket costs $2. Less if you buy in bulk or get a pass.
Also, you pay less in taxes (income and sales tax) since you're in NJ.
If you live in NJ but work in NY don't you pay NY taxes? And even if you want to get around that somehow, won't any normal employer payroll withhold for NY before you even see it?
Stuyvesant Town may be the biggest real-estate default in American history but it is really really nice. We have our own reading rooms, movie shows, ice-skating in winter, gym, 24-hours security with video, etc. It's just worth checking out the website http://www.stuytown.com/.
Disclaimer: I live here with roommates but have no other affiliation with Stuyvesant Town.
Anyway, the west side of Harlem, the other side of Morningside Park, has gentrified significantly in the last 20 years and is also by all accounts a pretty nice place to live nowadays.
Washington Heights is also "up-and-coming", up north of there.
Places like: Prospect Heights (A,C,2,3), Long Island City (7,N,R,Q,E,M,F), Lefferts Garden (Q,B,2,5), Astoria (N,Q), and Woodside/Jackson Heights (7,M,R & LIRR).
You may not be able to find a place to buy $6 PBRs or $5 coffees right around the corner, but I consider that a plus.