Robocop, enjoy your visit to NYC.
I lived there for a dozen years, until about 3 years ago. One of the things that struck me most about New York was how many of the TV shows are set in NYC. I never really thought much about where a lot of them were set, but you'll see so many iconic things that are all in New York that you've seen for years in TV shows and movies.
One thing I always recommended to people (and I think you'd appreciate it, with what you said about seeing how that many people get around) is to go early in the morning - 7 a.m. or thereabouts - and get to one of the denser business areas. I used to recommend being across the street from the World Trade Center, but now I guess I'd recommend the Wall Street area - perhaps near the bull?
Get a cup of coffee and a bagel or whatever, and find a spot on the fringe - hopefully where you can sit. Then just spend a half hour or hour watching how the streets come alive with people as you approach 8 and then 9 a.m. It's kind of like watching bees swarm to a hive, fish move in schools - that kind of thing, but it's people. The WTC used to house something like 50,000 people...so if you were to get there early and watch, it was like watching a decent-sized city become populated with people. I recommend you definitely ride the subway, but it's a LOT more pleasant if you stay off the trains during the heaviest crush of rush hour...that's usually not a lot of fun.
The Museum of Natural History - absolutely one of my favorite things. I used to be able to go there on my lunch break and get in for free (corporate sponsorship)...there's something for everyone there, but the trick is getting an idea of what you like so you can linger on that. For me, the animal dioramas are magical - it's like what virtual reality wishes it could be some day. If you stare at them, you can just almost see the animals breathe. Next best for me is the oceans hall, with the blue whale hanging overhead. Then, of course, people love the dinosaurs. The problem, as with most of NYC (if you want to call it a problem), is that you could spend a couple days easily working your way just through the museum, not counting the planetarium.
I'd suggest you pace yourselves a bit, and also try to group the things you're going to see into walkable clusters. Don't expect to see 8 things in one day taking the subway downtown, then uptown, then back and forth with major walking at each location. Try to plot "we take the train in from Tarrytown, arrive at Grand Central, take the 4/5/6 line downtown to Wall Street, get out, see that, walk around, then cross to Rector St. stop and take the 1/2/3 uptown to Houston (pronounced How-stun instead of like the city in Texas) and walk around Greenwich (Grenn-ich) Village...etc. etc.
Plan to walk WAY more than you usually do, unless you do a lot of foot patrol. You might like to bring a daypack, and some bottled water. There are some great Manhattan folding maps, laminated, some of which overlay street and subway lines, and the details of Central Park - very worthwhile, as some things can be a little tricky to find.
While I think you'll really like things like the museums, Broadway show, etc., I think you might like to do some less traditional things to round out your visit. Times Square is worth seeing for the sheer spectacle, but walking all up and down and trying out the retail stores there is much more like being in a huge mall than experiencing NYC. I find the little shops and street vendors way more interesting than the big-box stores that are everywhere - Virgin Megastore, Toys R Us, etc. (OK, Toys R Us is worth seeing just for the entrance area and the dinosaur, but nothing more). The Statue of Liberty is great, but it's such a LONG journey to get across to it - huge lines, then the slow boat across, huge lines, you can't go up inside the crown anymore, huge lines, slow boat return. If you're into genealogy and/or have a family connection, Ellis Island can be great, but otherwise, a huge portion of your time will be spent waiting, looking at bored, anxious tourists rushing to get back for a show. Seeing how people live and move through NYC will teach you a lot more about the city than seeing thousands of other tourists looking at the same thing you're looking at.
Instead, try walking Canal Street from west (starting around 6th Ave. or so) to east, head north to hit some of Little Italy, then south down Mulberry and into Chinatown.
My restaurant suggestion in Chinatown would be Shanghai Cuisine at 89 Bayard on the southeast corner with Mulberry. Every bit as good as Joe's Shanghai (in my opinion) and better on some of its food, it's smaller and perhaps a bit less of a tourist destination than Joe's Shanghai, although when I went last year it seems it's become more well-known. I would absolutely recommend the crab and pork tiny buns, aka the soup dumplings. It's just a Chinese dish you're unlikely to run across in the vast majority of the Chinese restaurants in the U.S. - unique and wonderful. There are comic strips on most of the tables that teach you how to eat them (if you just bite them, it's like a pizza cheese burn on all surfaces of your mouth). They have a lot of other wonderful dishes - their pork shoulder in brown sauce is fantastic, but your girlfriend's probably not going to be into that, and that's a portion for several people to join in. Scallion pancake, eggplant in garlic sauce - lots she might choose.
Within the same block, same side of the street, there's the Chinatown Ice Cream Factory - 65 Bayard. You'll get some unusual flavors like mango, mung bean, ginger, green tea, etc. They give BIG scoops - plan accordingly.
For Italian desserts and coffees, there's Ferrara Cafe on Grand between Mott and Mulberry. It's a huge tourist draw, but the pastries are pretty good. Or, Veniero's at 342 East 11th Street (between 1st and 2nd Avenue).
For steak, I'll agree with one of the earlier posters - Peter Luger Steak House is far and away the best steak I've ever had. Very old-school, worn floors and tables, it's all about the food. I went with a bachelor party of foodies - we got the steak for two, three times over, one rare, one medium rare, one medium. Sigh. Good times. However, if your girlfriend's a vegetarian, this might not be your best stop. There's very little for her there. If you do go - save your pennies.
Brooklyn - Brooklyn's fantastic - my first and last homes in NYC were in Brooklyn. The promenade in Brooklyn Heights will give you some of the best views of lower Manhattan, very lovely at night. Park Slope has its wonderful old Brownstones, and I actually like Prospect Park way better than Central Park (biased from having lived near it so many years). However, you'll run into the same problem - trying to fit so much into the amount of time you have.
People have had tons of great suggestions - I think you'll have to pick and choose those things that appeal most, and try to plot out with a street and subway map how to tackle them - and probably expect to have some things you'll have to drop from each day's plans.
Enjoy it
Dave
1 year later not gettin away that easy , ya think we just gonna fuggedaboutit , just when you thought you were out we pull you back in 
