I always have a few NYC things to do...
Picnic in Central Park....even if it's chilly.
I love the Zagat guides for food.
Head to Upper West Side...(near 80th) ...H&H BAgels and then to Zabars for some smoked Salmon and cream cheese or what ever goodies float your boat.
Touristy but good is Katz's Deli. One sandwhich feeds two...just don't go Meg Ryan and scream at the top of your lungs.
Ditto on the Queen's area...love the Greek food there.
I am a sucker for NY style Pizza.
Do all the crazy touristy things if you want. Those are pretty well known. Empire State is a pain in the butt to have to wait for, but it is worth it.
If you take the 1/9 (double check this) train up going north to the end there is a nice little park called the Cloisters. Very nice and they have managed to bring over almost an entire Church from Spain. It's a nice getaway from the manic city if you like.
As for accomodations we always do an unhosted B&B. Abode Bed and Breakfast and City Lights both can book for you (search yahoo), but do it ASAP. VERY ROMANTIC! They have cheaper ones and more expensive ones let them know your budget. It's nice because you get a little kitchen and it's one way to save some money. The Suites that some hotels have are not bad either. Check out places like hotels.com for them.
um... we also like to do the comedy clubs sometimes and God...the whole area is just great.
I have always had a connection to New York for some strange reason... and my husband even did the first part of his proposal to me on the top of the Empire State (long story as to why there are two parts) so NY is even more special now.