I've only skimmed all the comments, so apologies if these suggestions have already been made.
1) Missoula, Montana. Winters aren't exactly MILD, but they're also not as cold as you might expect. They're almost certainly warmer than Pennsylvania. Summers are milder as well, due to low humidity. While the COL is a bit high for Montana, it's low relative to the country in general. And it is GORGEOUS! Lots and lots and lots of outdoor recreation opportunities, if you're into that. It's always been on our list of top five places to live.
2) Blacksburg, Virginia. Because it's in the mountains, the summers are not nearly as hot as elsewhere in the region. Winters are a bit cold, but not extreme by any means. The presence of Virginia Tech drives the COL up somewhat, but it's still pretty low. The town itself is getting quite a bit cooler. When I lived there, we spent a year living in a super-awesome cohousing community, which I'd definitely recommend checking out.
3) Boise, Idaho. This is a new addition to my list. Parts of town are more liberal than others, to be sure, but if you are anywhere near the downtown / north end / northeast side of town, you'll find some great spots and some great people. Boise is really turning into a great little city, but is still quite affordable. Climate is pretty mild, airport is pretty affordable, lots of outdoor rec opportunities, etc. I like it a lot.