You're gettin a lot of good recommendations. But one thing: you forgot to mention your budget. NYC has some of the best restaurants in the world, and the prices to go with them. That said, you can find some amazingly good restaurants that aren't flooded with tourists or people looking for the "hot place of the moment" that are relatively reasonable in terms of price.
I left the NYC area 6 years ago, so I'm no good for the new places. If you want a sit-down pizza experience, you have to go to Lombardi's, Arturo's, or John's (or all three, lol). For a slice on the go, take your pick. You can't go too wrong (if you ask 100 NYers where to go for a slice, you'll get 100 different answers, lol).
For the average person, there are probably some BBQ restaurants that would be decent (and even praise-worthy). But for the people in this forum, I wouldn't waste much time looking for BBQ in NYC. You'll be shocked at the prices and underwhelmed by the food. NYC is known for a lot of things, but BBQ is not one of them, I don't care what people from NY/NJ say. Looking for good BBQ in NYC is like going to Little Rock, AR and looking for a lobster shack. Its just not what they are known for.
Be sure to getchya soft pretzel from a vendor on the street (and maybe a hot dog or two if you're into hot dogs).
For desserts, head for Little Italy (any cafe in that area will do). You can also get a good Italian meal in Little Italy, though it is VERY touristy.
I would also take a look at reviews on yelp.com for other restaurant recommendations. You can specify a specific type of food, neighborhood, price range, etc when you do a search.
Have fun!