Former NYC painter
I was in NYC until a couple of years ago, and I started a yahoo group called NYC_mini-painters for those of you who might be interested. I still meet up with my friends from the group at Gen Con.
When I left, there were three GW stores in Manhattan, one on Broadway and 8th, one on the Upper East side on 1st somewhere and one on the Upper West side. Forbidden Planet had stopped selling minis, but they were still a great place for lots of other goodies.
There was also Neutral Ground, a true gaming store. They actually had gaming tables, though there selection of stuff was not excessive. I forget exactly where they were, somewhere on the west side near 23rd I think (Yes, I haven\'t been back to NYC since I moved

) . Then there was the Compleat Strategist, and they had an excellent selection, but little room for demos or anything like that. That one is near the Empire State building.
Most of the time though, we ended up going out to Jersey or Long Island for our mini fix, just because, like someone else mentioned, rents are high in NYC, so stores there are thing on the ground or sell mostly high margin stuff like GW and card games.