Think college towns. I spent a weekend in Asheville and loved it. My wife went to VT and I have hence been to Blacksburg several times. It is kind of isolated but very inexpensive and has a lot to offer given the large university presence. Charlottesville (UVA) may also be nice but I'd avoid the DC area where I live--crappy weather and terribly overpriced like much of California where I also used to live (in both So Cal and Nor Cal) and agree that for long termers it is cheap but newcomers get screwed on property taxes and a lot of other things.
If I could I would just immigrate to Vienna, Austria, it always ranks high on charts of places to live and after spending some time there as a student I agree.