Hmm…the “New West” referenced in my OP is Futuristic, with robots & other high tech, oddly transposed with Western cultural values & the semi-anarchy of the Frontier.
You may have been mislead. Sorry about that, Evil Captor.
The short story “Spud and Cochise” by Oliver LaFarge, 1957; reprinted in the 1980 anthology The Best of All Possible Worlds (Spider Robinson, ed.) – http://www.amazon.com/gp/product/0441054838/qid=1136175357/sr=8-1/ref=sr_8_xs_ap_i1_xgl14/103-2231941-5334243?n=507846&s=books&v=glance.
Two of my recommendations have already been mentioned; Mark Sumner’s Devil’s Tower and Devil’s Engine and Oliver LaFarge’s Spud and Cochise - all very good.
And great news. I was going to recommend a old comic book series called Tex Arcana by John Findley. I was going to tell you how great it was but then I was going to have to tell you it had been out of print for about twenty years. But I did a Google search and found that Findley now has the entire series posted online here.