Hit NYC for a few days, enjoy the City, then head - in stages - through upstate NY.
Take Metro North Train http://www.mta.info/mnr/ from Manhattan (Grand Central Station) http://grandcentralterminal.com/ to Poughkeepsie. From Poughkeepsie, make your way to New Paltz, NY - head to Mohonk Preserve http://www.mohonkpreserve.org/ for hiking, rock climbing, bouldering (Bonticue Crag)for very little expense. It's a great town with lots of great food choices & relatively inexpensive places to stay.
From there, if you are feeling adventurous, take train / bus up to the Adirondecks for backpacking into the "wild" or - Lake Placid area http://www.lakeplacid.com/ for great camping/hiking, skiing in the Winter - just lots of nature, OR make your way North and West to Niagara Falls. / Canada.
You can stay at camp sites or in cabins up north, and hostels in NYC and inexpensive hotel/motel in New Paltz areas.
New York is beautiful, and much, much more than just NYC.