Given your criteria, Knoxville’s not a bad choice (though once you’re outside the UT orbit, left-of-center politics might be tough to find among the locals).
The first place that came to mind was actually Chattanooga. It’s still got a lot of small-city feel to it, they’ve done a fabulous job of revitalizing the downtown area, there’s more stuff to do than my family and I have been able to get around to after four or five weekend trips there in the last three or four years, and the cost of living is relatively low (last I checked, I could expect to live in Chattanooga for about 82% of what it costs me in Atlanta).
It may be a little light on culture (the Walker Art Center seems to have some creative exhibits, but I can’t speak for the quality of the libraries, etc.), and I don’t know whether UT-Chattanooga qualifies as a “university” in your meaning of the term, but Chattanooga seems to be attracting a young, hip, culturally-oriented population these days, so I think the cultural scene is only going to improve. Plus you’re only 2 hours from Atlanta and 2.5 or so from Nashville – so that not only do you have access to nearly any cultural activity you’re interested in, you can also fly to nearly anyplace in the county and most places around the world on direct flights (since Nashville is an American Airlines hub and Atlanta is a Delta hub). The climate is quite garden-friendly and the winters have been extremely mild the last several years. The population may not be quite as diverse as some larger areas, but there’s a pretty reasonable mix of white, black, and Latino, with Latino being the fastest growing group (the proximity to the carpet- and construction-industry jobs in North Georgia being a big reason). There’s lots of hiking and camping opportunities very close by, and it’s only an hour and a half or so to the Great Smoky Mountains National Park.
The main advantages of Chattanooga over Knoxville are size and access; Chattanooga’s a bit bigger and it’s a lot more accessible to the rest of the world (either by plane or car). Culturally, Knoxville would have a slight edge considering only local resources, but the proximity of Chattanooga to Atlanta and Nashville might balance that out (it’s four hours or more from Knoxville to either one). I’ve spent a fair amount of time in both places and was actually close to moving to Knoxville at one time, and I’d definitely prefer Chattanooga; UT dominates Knoxville so completely that if you’re not connected to it, you feel cut off from most of the people around you.
Another possibility would be my wife’s hometown, Asheville, NC. Very left-leaning younger population (which causes some friction with the old-timers and business interests). Museums and libraries may not be up to the level of other places, but you’ve got LOTS of artists, craftspeople, musicians, and other creative types. Wandering around downtown Asheville these days is like visiting a permanent arts festival. The altitude makes it a bit colder in the winter than Chattanooga or Knoxville, but it’s still quite mild by comparison with northern states, and the compensation is that it’s quite possible to sleep with the windows open most nights of the summer without sweating all night (my mother-in-law refuses to turn on the A/C for anything, so I speak from experience here). UNC-Asheville isn’t a world class university, but the undergraduate program is a pretty good liberal college, and there are a few other small colleges in the surrounding area to add flavor. Needless to say, the outdoor recreation opportunities of western North Carolina are nearly unmatched, particularly for camping, hiking, and rafting/canoeing/kayaking. The downside is that it’s been a hot place to move for a bit longer than Chattanooga, so it’s more expensive to live there; I’ve actually seen some estimates that put the COL there at or above Atlanta’s, though I think that’s too high based on my experience.
Charlottesville, VA, is also an excellent suggestion, and depending on the importance you attach to the quality of the university and the number of museums and libraries could be the clear winner. Where it (and Knoxville) come up short for me is in the degree to which the university dominates the town. Chattanooga and Asheville would continue to be more or less what they are with or without the fairly undistinguished institutions that reside there, while Charlottesville and Knoxville would be utterly different without UVA and UT. Fifteen years ago my attitude might have been exactly reversed, but now that I’m in my late thirties I don’t necessarily want everyone I see in my daily rounds to be either a college student or professor – if I’d wanted that, I’d have finished my Ph.D. in English.
Another small city that impressed me in my one brief visit there was Roanoke, Virginia. Southwestern Virginia has many of the same advantages as eastern Tennessee and western North Carolina, and it’s a pretty inexpensive area still. The downside would be cultural; my impression is that there’s not nearly as much going on there as in the other candidates. It should qualify on other counts, however, with the exception of a university (Roanoke and Hollins are good, but not quite the same as UVA or UT). The population is comparable to the other cities mentioned (just under 100,000 in the city itself, about 225K in the MSA).