I would not suggest staying in Valdosta or near the border. Did that one year, and everything was just lousy.
Last year when I made the trip with my aunt from Indiana down, we stopped in a town off of I-40 to have lunch with relatives. So I continued south on I-40, took some state roads and drove through the Smokey National Park. Took 64 over towards Blairsville, GA and then south from there back to I-75. It's absolutely beautiful if you don't mind the scenic tour, which added a few hrs of driving to the day.
Don't forget to use the 475 to go around Macon.