At least during their business hours, any Barnes and Noble location really is the way to go.1 They don't control entry to the store beyond having you check your bags, and then the whole place is at your disposal. There are often restrooms on every floor, and compared the shit-smeared loo of your average bar or McDonalds, the Barnes and Noble WC's, especially the ones on higher floors, are operating rooms. This means that the B&N stop is even an option for doing number two, or even number three, if number three ever presents itself as an emergency.2 In any case, you can even take reading material if that is your cup of tea.
Convenient Barnes and Noble locations are:
Manhattan:
Union Square, north side
Astor Place
Fifth Ave and 18th street
Fifth Ave and 51st street
Broadway and 72nd
Broadway and 81st
many others...
Brooklyn:
Court Street two blocks north of Atlantic
Seventh Avenue and Sixth Street in Park Slope
Unfortunately, many NYC restroom emergencies present themselves at hours when Barnes and Noble is not open. If you are a guy looking to do number one, your best option in my opinion, is to unload on the street with the payphone technique described above, or simply find a secluded corner by a dumpster on a street (never an avenue!).3 If your act involves sitting, however, you are, in my opinion, in a lot more trouble.
In any case, I have to recommend against using any fast food places' restrooms. Homeless people and anyone looking for a place to shoot heroin have thought about this long before you. Once I made the mistake of ducking into the Union Square McDonalds, and what transpired still makes me shudder and dry heave: There were several people in line for the one restroom. We all just waited and waited. The woman at the head of the line eventually knocked on the door and an angry female voice inside said "What? I'm taking a shit in here, alright." Then her fat reeking form actually opened the door, leaned out while still butt ass naked, and said to the woman who had knocked "I'm taking a shit in here, ok? ooooh, I'm sick! Oooh..." Then she closed the door. About five minuted later she opened the door and exclaimed something before bolting out. Everyone ahead of me in line began running wildly for the exit, and when the stench reached me, I did as well.4
By the way, in New York City, vomitting is not considered an activity that has to take place in a restroom. Feel free to do this on the street, preferable projecting as far as possible for the amusement of onlookers. But please don't vomit on the subway.
1ha ha. Pun intended.
2If you don't think number three can be an emergency, you haven't seen how short the skirts can get in Manhattan on a really hot day in the summer. Yowza!
3Supposedly the penalty for public urination, for a first time offense, is a $50 fine.
4and remember, the hands that clean these restrooms then go on to assemble your mad cow burger.