P.S:- Steve Jobs took a break in India, if you are looking for precedence.
Within the US, basically anywhere that isn't one of the stereotypically expensive cities is cheap. In California, it's dirt-cheap to live anywhere that isn't in the SD, LA or SF areas; San Luis Obispo and Eureka are decent coastal options. Anywhere in Oregon outside Portland is also cheap. Among cities, the midwest rust-belt cities are cheapest, e.g. Pittsburgh, and pretty interesting.
And then I'll say if you are considering Eureka, CA (or Arcata, CA, ten miles away), I will heavily recommend Corvallis, OR instead. I've lived in these places, and the difference in the attitudes I get from people is amazing.
Oddly enough, after I moved to Corvallis (from the east coast) is when I read that essay, which led me to reading all his other essays, and to reading Hacker News!
Back to topic, most small towns feel stifling to me; you may be fine with what entails but I need some socialization, and what PG says about how cities (and towns) can influence the inhabitants seems to hold true, or at least it seems to hold true for me.
Best of luck to OP where ever your travels take you!
Does it have to be an urban area? Almost any rural area should be relatively cheap, and if it's not too far from a major city, you could make a trip there once in a while for the "culturally interesting" part.
Awesome Internet access, amazing food, great culture, the nicest people. "Backpacker" cost of living is under $500/mo, and "Expat" cost of living is under $4000/mo. (For those who may not be familiar with the expat lifestyle, it includes niceties like a driver and a cook.)
My wife and I lived in Southeast Asia (several cities) from 2002-2004. In the interim, the infrastructure has gotten even better and the prices have remained flat.
I know several Facebook app developers who have moved down there and are living like royalty for $2500 / month.