As per Bob, I once went from seeing the skyline in Harriman state park, to seeing a big black bear a few miles later on Chipmunk mountain.
Those maps he mentions are excellent. I’ve since moved from NYC, and I miss the nice maps.
Fahnestock State Park is also fairly close and has some nice trails. Overnight camping is restricted.
If you are headed for a quick overnight in the Catskills, the Denning Rd trailhead, and Neversink River, is a nice quick hike with nice camp spots by the river.
Also: Fire Island. You park in or take a train to bay shore long island, take the ferry out, and then walk through all the houses on a boardwalk (its a no car island), then past the campground, where you drop off your permit, then down the beach a few miles (5? I forget…), and you can pitch in the dunes, wilderness style. They campground has plumbing etc, but its worth getting the permit to go down the beach. The catch is that you gotta carry all of your water. I think you could also rent kayaks and make your way out on the bay side if you want, but I didn’t do that. Early spring would be a good time, but if you’re interested, research available permits immediately.