Josephines (although a bit far away), Cite and Le Bernardin are all great suggestions although quite different in both ambience and price. I think Petrossian is also quite close to there and is very nice also. Petrossian is much smaller than the other restaurants mentioned with an extremely friendly staff for a relatively formal place. Another might be the Manhattan Ocean Club which is a nice restaurant with excellent seafood, but is a bit pricey, although not as expensive (or as good) as Le Bernardin.