7853H
Not quite sure what you are picking up, but if the elevation isn't a problem, you may want to think about Taos. Beautiful scenery around that area (from Rio Grande Gorge to the ski area and mountains). Taos is a fun place to visit. The airport is a ways from the town, but plenty of transportation options.
I would also echo Durango or perhaps Pagosa (both right on NM and CO border). Both places are beautiful and fun to visit. Just watch the density altitude.
If you are looking to camp, consider Navajo Dam (1V0). There is a strip on the west side of the dam. Not a very scenic spot itself, but it is within a reasonable walking distance of the San Juan river, which has some of the best fishing anywhere. Have made a few day trips to the San Juan, and it is always enjoyable (just a bit of a hike back up the hill at the end of the day)! If your not into hiking and doing it yourself, you can get guides to pick you up at the strip and bring you back. Look at Duranglers website out of Durango for info.
Regards, Larry