Have you considered the G&T programs at the public schools? They are very competitive, but can be great from what I hear and are quite a bit above the standard level of public school education. Karen over at
www.TestingMom.com makes her living helping children get into G&T programs, she is based out of NYC I believe, and this was posted on her site:
http://www.testingmom.com/blog/nyc-gifted-testing-story/ (part one)
http://www.testingmom.com/blog/a-mothers-testing-saga-part-ii-the-finish-line-by-anna-li/ (part two)
You also may be interested in checking out this website, not sure if it will he helpful on your search or not:
http://www.davidsongifted.org/ And this is an older article, but it might give you some leads/insights.
http://www.nytimes.com/2009/05/05/education/05gifted.html?ref=giftedstudents And the general website for info-
http://schools.nyc.gov/Academics/GiftedandTalented/default.htm &
http://www.ps85q.org/gifted.htm And this article mentions School Search NYC, a private advising company.
http://www.nytimes.com/2009/10/19/education/19gifted.html?pagewanted=allGood luck, if I come across anything else I'll add it in. Let us know how it turns out, looking for a high quality yet affordable school (especially one with a G&T program in NYC) can be a huge challenge!