Walking in NY is a breeze.
La Boite en Bois at 68th & Columbus is a little French walk-down with very few tables so they are close together.
Many people who have shows or opera at Lincoln Center frequent this little charmer.
It is not pricy as NY restaurants go.
It was also featured on Seinfeld.
There will likely be lines at most places on a Sunday, unless you go early, but:
Good Enough to Eat: Amsterdam and 83
Nice Matin: 79 and Amsterdam
Simply Oliver: 82 and Amst, I think.
Fred's: Amsterdam and 83
or, if you don't mind eating non-typical brunch food
Canteen (Chinese with some Thai influence) Columbus and 83.
Momoya (Japanese, mostly sushi) 82 and Amst.
AG Kitchen (Cuban): Columbus and 74
More high end:
Atlantic Grill (seafood).