Depends on the route you go. Dothan is probably the best mid-way point if you're going through Alabama and avoiding Georgia. When we drove from Memphis (former Memphis and proud U of M alum), we took the route through Atlanta. If you do this, I would say that your best midway point might be Macon, GA. As I recall, Macon looked like a decent area as we drove past and you'd likely find a decent chain hotel near the interstate.
We chose the route through Atlanta because it is all interstate from Birmingham on in and having driven through southern Alabama many times, the route from Birmingham down can be slow at times. Plus, at the time there were some major detours (but this was years ago, I'm sure the roadwork is done now) and we drove straight through at night, so I felt more comfortable on the interstates.
If you use Google maps and enter Memphis to Orlando you'll notice the route through Dothan (US78-E) is about 30 miles shorter than the route through Atlanta (US78E and I75S), but time-wise it's minimal because of the faster speeds you can travel going through Atlanta.
All in all, the drive wasn't bad. I think it took us 14 hours total, but at one point we had to pull to a rest stop and sleep.