You need LCOL but high wages. Here are some good candidates -
Tampa
Phoenix
Durham
Ok City
KS City
Omaha
I have lived in Tampa and while most things are LCOL, the housing is not in Tampa, and it's getting so much worse. Also in the recent years the city has been flooding due to heavy rains and an outdated drainage system (BAD combo for a city on the Bay, where it rains, and is suffering from effects of climate change), so flood insurance is often required and insurance in general, is higher than the rest of the country. When I worked in downtown, it was particularly bad, so bad that for an entire week my job either had us telecommute, or let us off early based on the rain prediction so that we could drive out of downtown (DOWNTOWN TAMPA for christ's sakes), without our cars floating away, because the streets would flood after only 30 min of rain.
And there isn't much to do there as it is mostly a business center, surrounded by sprawling suburbs. If you have kids there are alot of things to do, museums geared towards kids, zoos, aquariums, theme parks. If you're into sports there's tons of that. But there is a lot of blight with only small, unconnected spots of safe and walkable areas; Tampa does not have "good and bad" areas (area implies expansiveness); it has good and bad streets. It is NOT pedestrian friendly (even, ESPECIALLY, downtown), tourists and people traveling for the many concerts and sports events, or thru Tampa to get to the beaches (there aren't beaches there; Tampa is the vestibule for St Pete and Clearwater, that everyone drives through to get to the beaches) maked the already horrid traffic worse.
And probably the worse thing was that there didn't seem to be a clear cultural identity, other than Gasparilla (like a pirate themed Mardi Gras), and a historic cuban culture that mostly centered on old cigar factories. There used to be more of a presence of old Tampa, but that got crowded out with chains and business/commerce and condos.
Also, personal disclaimer: I hate the beach, and flooding and rain and general wetness, and being hot all the time, and crowds. I am much more a mountains and woods and seasons type person, so I may be a bit biased.
You don't like the beach and you're more of a mountains and outdoorsy person? Geez, can't imagine why you wouldn't like the Tampa area. You sound like someone for whom Outside magazine is forever writing another version of its best-places-to-bike-and-drink-craft-beer stories.
I've lived in Tampa 22 years. Came here at 28 to escape the traffic, cold winters, state income taxes and general insufferable people of DC/MD/Va. Here's what's great about Tampa Bay, in no particular order.
1. Best Airport in the country, hands down.
2. Awesome weather.
3. No state income tax.
4. Negligible traffic. (I lived in NOVA until age 28 and have spent lots of time in Atlanta and LA. Tampa traffic on its worst day is better than an average day in any of those three.)
5. We have some of the highest-rated beaches in the country by Dr. Beach, the dude who does those ratings.
6. If you're a triathlete, this might be the best place in the county.
7. Ditto for stand-up paddle boarding.
8. Fishing, boating, awesome. Pinellas County is surrounded by water.
9. Tarpon Springs -- largest concentration of Greeks outside of Greece. The Sponge Docks district feels like you're on a Greek island.
10. Spring training baseball.
11. LCOL - If you're looking for a cushy, six-figure corporate job, this is not the place for you. But if you're a self-starter or someone who can work anywhere, this is absolutely the best place to be.
12. Awesome place to raise kids. Public schools are not great BUT they have many magnet, gifted and other options. My kids could go to literally a dozen public high schools. We have friends in St. Pete whose daughter drives an hour each way to school in Tarpon Springs because it has a high school veterinarian program. Public school.
13. A dozen little beach communities, each with its own character. (Oh yeah, that beach thing again.)
14. It has a wonderful funky nature to it. Yes, it's full of people from Carl Hiaasen and Tim Dorsey novels - Dorsey lives here, too - but if you want homogeneity, go live in freakin' north Atlanta.
15. Ybor City? Please. St. Pete has been the more popular nightspot for more than a decade. If nightlife and craft breweries are your thing - not mine, but I get it - St. Pete is awesome.