Perhaps you could add some sort of hysteresis such that it continues to report you as being in the previous grid square unless you go >1/2 a grid square distance away from it

It could use neighborhood. Use GPS to locate your neighborhood then give your location as the townhall or central park or whatever in that area.

Changing what you use as the boundary doesn't change the fact that if you're close enough to the actual boundary, you will jump a lot. So you have to go quite large with the boundary for it to limit the pinpointing. Having larger areas within your boundaries makes the feature much less 'useful' though.

Which granularity: Harlem/Hell's Kitchen etc? West Harlem/East Harlem etc? Manhattan/Long Island? New York/New Jersey etc.?

Feature wise you would probably want at least something like Harlem/Hell's kitchen granularity and there are unfortunately enough people living on the borders of all of these that you could pinpoint those just from GPS inaccuracies.