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).