and to answer the OP's question: MISSOULA, MONTANA. Very progressive, the most literary/art-friendly city in the region, great running trails, beautiful country.
second place would have to be san francisco. obviously it's not 'new' in the way that missoula is 'new' but it is a progressive city and you are on the edge of the multiple beautiful habitats: the biggest ocean in the world, hundreds of miles of forest and hills, not far from wine country and the desert. it's paradise.
third - look at big sur. not really a city, but take a look at it. other candidates: in the rockies - boulder, colorado. steamboat, colorado. in the cascades - seattle, washington.
i don't think you can think of a city in north carolina or texas as a running paradise because of just how bad the weather is going to be. missoula will be a little cold (better in my book than too hot) but if you are looking for year round moderation, go for san fran.