Right off, I'd suggest skipping the big cities unless there's a reason you want to go there. The traffic is much better if you give Nashville and Knoxville a 60 mile berth. That said, there are a few routes that get in close to downtown without too much hassle.
You'll be coming in a bit north of the Natchez Trace, which gets you close to Nashville. Sorry I can't help with north or west of there.
Going east from Nashville, I'd suggest looking at some of the RUSA rides. For instance, starting south of Nashville:http://ridewithgps.com/routes/2274439
until it intersects with:http://ridewithgps.com/trips/1826725
Randonneurs generally have a good handle on good cycling routes (except when they throw in a climb just for fun!).
From just above Cheoah Dam (where the dam scene was filmed for The Fugitive), you could take NC 28 past Fontana Dam (highest dam east of the Mississippi) to 19/74; or if you do the Cherohala climb, you could basically coast down from Robbinsville to 19/74 and then down through the Nantahala Gorge (DO NOT RIDE THIS ON A WEEKEND! People will be watching the rafters instead of the road.). Either way, you've got a few miles of stiff, busy climbing up to Bryson City. Then take the old road to Cherokee, and from there take a couple days to climb the Blue Ridge Parkway into Asheville.