It's always hard to try to throw out piecemeal suggestions. Santa Fe/Albq vs. Sedona/Tombstone really would also depend upon what else you want to see and do.
You'd mentioned grand circle, which generally refers to Utah, at which point heading towards Santa Fe would probably make more sense. Also, your references to "cowboy towns" and "vast deserts" makes me think you're probably looking for settings that are more like movie sets than real life, but as such, Monument Valley might be an ideal stop. That would be much more on the way to Santa Fe.
I think you're at the point where sketching out a rough itinerary is going to be important to help you figure out what places work best, and how many places you can actually go with your fairly limited amount of time. That's especially true since it sounds like in reality, you've actually only got about 10 exploration days, once you factor in airport time and jet lag.