If you're not strictly wedded to the US, one possibility from NYC would be to head north to Montreal. It's got culture, art, and history in spades, and the food scene is excellent. The city is extremely walkable and also has a comprehensive and efficient public transit network. It's also a reasonably priced city by international standards.

You can get there easily from NY by bus (6-7 hours) or train (11-ish hours, but dirt cheap and with drop-dead gorgeous views), or it's maybe a 1.5-hour flight.

You could also do Quebec City, which is a historic gem and (IMHO) tied with San Francisco as North America's most beautiful city. The food there is also excellent.

The weather in both cities at that time of year should be quite lovely, with warm days and nights that might be just a touch on the chilly side.