What about Tucson?

Relatively inexpensive, and if you choose your location wisely, possible to rely on a bike pretty exclusively- if you can avoid midday trips between June and September. I am able to make it through a 10 mile commute once a week even in the summer- but afternoons can be a little bit brutal at times. If you were more centrally located, it would be possible.

We have a good bike lane system, though not as good as somewhere like Seattle. Warmer than Colorado in the winter....