Go to Chinatown and do a dim sum brunch. The waitresses wheel carts full of food around, you point at whatever you want, and they give it to you. Adventurous, different, and usually very tasty.
My favorite place for this is upstairs from a shopping mall under a bridge, and virtually impossible to give directions to. But maybe some other NYC dopers (or an NYC eating website) will have recommendations.
I was going to say Veselka, but that’s EV, not very good, but good mural on the wall. Just do like everyone else does, grab a bagel and some shmear, a coffee to go, and get to business.
I somewhat agree with above, though I don’t remember the name “L’abeille” – but there’s loads of places in Chelsea where you can get a giant mug of coffee, and some good pastry. For good, you’ll have to walk down a 0.5 mi or up again, is my recollection (from midtown ETA).
Also ETA – grab a muffin and some coffee, and wait 'til lunch for some crazy-ass pastrami sandwich or whatever you want. Or some blocks down in WV (maybe 20), go to a Cuban-Chinese diner and see if (a) they’re open and (b) if you want to chow some of what they want you to eat for breakfast.
Le Pain is nice, and different, but not very New York. I think of it as an LA place (my former home town) even though it isn’t any more Los Angeles than it is NYC. But it’s good for a nice casual quick sit down breakfast. Their baked goods, as you would guess, are fantastic. As are their jams and spreads.
A quibble, though. It’s not “one of the quintessential New York bagel shops.” It’s the best damn bagels you’ll ever eat in your life. Crispy on the outside and soft on the inside. Heavy as hell, yet somehow fluffy. And often you’ll be buying them hot out of the oven.
Sadly, though, you can’t take them home with you (if home is out of town). Grab a table at the restaurant, take them back to the hotel, or find a sunny park bench, but eat them quickly. After a couple of hours, they’re almost inedible.
Ess-a-bagel is pretty good, even very good. It’s probably the best bagel place in Manhattan. Personally, I’ve had better.
If you really want an experience go down to Kossar’s bialys. The bialy is a near relative of the bagel which is even more greatly misunderstood by the bread making masses. They aren’t glossy or crusty and the hole doesn’t go all the way through. The dough is more lofty, with holes, than a bagel (which should be dense and uniform). mmmmm, Kossar’s.