coming from NYC, i suggested small towns. for sheer beauty, visit Zion National Park. I think it's called Springdale. again, a small town. Santa Cruz was the largest "city" I listed. And Sedonna is a nice place to visit, but it's been heavily developed in the past few years, so traffic can be a bear. You might like Santa FE, NM, but I found the streets to be too small, and no parking anywhere.
JMedeiros,
Flagstaff may have changed since you last saw it. Once they put up that 1000 room Hotel things just don't look right. The olde part of town is nice, but the rest I didn't care for. Now if you take the old road from Flagstaff to Sedonna, well that's a different story. Too bad that the ski season, in Flagstaff, is a bust. I also heard that radioactive waste is being stored at Mt. Humphrey. Go up the road to Kaibab National Forest, on route 180 and you'll be pleasantly surprised.
If you ever want to be reminded of Vermont or New Hampshire, seek out Monarchy Pass, Colorado. It seems like a hundred miles of unbroken tree lines. Ski country. VERY small cow town (Gunnison). You'd better be a farmer or cowboy, though. And of course Montana has some really beautiful countryside.
And of course there's the Million Mile Trail in Colorado. Just don't settle in Telluride. Too much lead dust. The natives are contentious when it's not tourist season.