<<Disclaimer: Verify this information before applying it to your situation.>>

Try the Palm West 250 West 50th St. I'm sure you have heard of The Palm, this is just an extension of the great steakhouse on the west side.  If you don't mind traveling across town, Sparks, Smith & Wollensky, and The Post House, or of course Leuger's in Brooklyn(but that's not in a great neighborhood) are all great steak places as well and it'd be a shame to come all the way to ny without going to at least one great steak place.  There are also many great French, Chinese, and Italian restuarants and I'm sure most Italian places will substitute gf pasta if you bring your own, just call ahead obviously.  If you are looking for any other cuisine let me know, my Dad's an expert on NYC restaurants.  

Check out the Outback Steakhouse web site that has a gluten free menu and a
location map.

*Support summarization of posts, reply to the SENDER not the CELIAC List*