I think that in the Southwest, network choice is a key part of selecting a cell-phone if you do any travel away from metropolitan areas. I have been much happier with service from those networks that are not ENTIRELY GSM-based in the rural areas that surround the city where I live. Services like T-Mobile and Sprint(PCS) just don't work more than 10 miles outside of my city.

Without delving into more technology, just take a good look at the network coverage maps of the providers you are considering. Also, the more "bands" your phone has the better. I haven't looked in a while but Verizon and AT&T seem to offer the best coverage but are also a bit more expensive.

(I have no affiliation with Verizon or AT&T)