Columbia SC to Dallas TX is a tough one. The most direct route is right across northern Georgia, Alabama, Mississippi, southern Arkansas and eastern Texas. Lots of bad roads and bad food (but plenty of nice, courteous people). The main roads in this area tend to have no shoulders, gravel shoulders or small shoulders full of rumble strips. Back roads would be much less trafficked but require a lot of careful planning and good maps. You would also have to skirt the huge Atlanta area if, like me, you avoid major cities.
IOW, you're saying the rest of The South is just like the Carolinas? Here's what I've learned in the past ten years:
- There are two types of pavement (if you don't count "crush and run" as pavement, that is): Asphalt and "chip and tar", which is basically gravel laid on top of tar which holds it together. I'm on an expedition type touring bike; long wheelbase, triple cranks, real low gears and touring tires. So these are usable, if not preferable.
- "...no shoulders, gravel shoulders or small shoulders full of rumble strips" is irrelevant, because the drivers all go around you. And I mean really around you, into opposing lanes if necessary, or wait until it's blatantly obviously safe to do so. All without horns. Probably because there are no shoulders. Roads with shoulders they tend to just whiz by, just like in the cities.
- Smaller "cities", meaning those with populations less than 100,000 are pretty much the same, and make pleasant POIs/stopping points.
- There are a lot of state highways which most city dwellers would probably consider "back roads", and are very pleasant to ride, as long as traffic isn't too heavy (see previous item on shoulders).
- The quality of the food is a matter of personal taste. And fast food is everywhere
These "back roads" would be my preferred route, actually. I would prefer avoiding really large cities (like Atlanta) whenever possible, as long as there are places to resupply and sleep. Camping is preferred, but I would like to use a motel at least once and a while. National Forest campgrounds are probably my best bet if the Carolinas are any indication, as I'm on a bicycle carrying a tent, not one of those Rolling Waldorf Astorias the "posers" in these parts call "campers".
If you could make your way to just south of Nashville you could ride the Natchez Trace (A ride on my to-do list) to Natchez MS. This would be a somewhat zigzag route but would make about 1/3 of your trip to Dallas very pleasant. I believe the Southern Tier goes through or near Natchez.
A little trick I often use is to follow highways that parallel interstates. They are usually lightly trafficked and have plenty of services.
Where is the Natches Trace (it's not a mountain bike trail is it)? I don't see anything on the ACA route diagrams in the South except the Underground Railroad Route, which is north/south. Naturally, I don't expect any one person to know how to get all the way across, which is why I am asking so early. But a bunch of pieces that can be linked together (or at least warnings of routes to be avoided) maybe I can put together into something enjoyable. As I noted earlier, I have the entire US available down to a scale of 1 inch = 500 feet. But no details about the "roads" themselves.
Edit: I found the natchez trail, and at first glance it does look good all the way from Nashville area to the Jackson mississippi area, which is directly east of dallas/FW area. So I have a feasable route to the middle of Mississippi, at least.