We're from Memphis, but go through Montgomery, so I thought I'd share...
We like the road less traveled. Less traffic. Less stress.
We do US78 from Memphis to Birmingham, I65 from Bham to Montgomery, then we do a quick jaunt on I85 towards Atlanta and get off at AL271/Taylor Road (We've tested this and it is MUCH quicker than getting off at the US231 exit!!). From there we take 231 to Troy, then turn right onto AL87 South. We take that through the FL stateline (there are 2 tricky turns in Elba, AL) when it becomes FL81. We take FL81 to a right turn onto FL20. 10 miles later we turn left onto 331. Then, we take a left onto 98.
It's worked for us everytime.
It takes us around 8 hours 15 minutes going this way with 2 good stops. I think Montgomery to the beach is 2 hours 15 minutes this way.