You have a great plan and a lot of miles in your program already. However, if you are interested in mountains, forests, and lakeside cabins you need to go Northeast from Atlanta. If you travel I-85 towards Greenville, then I-26 N to Route 74 and drive to Ashville, this is the most scenic section of the Carolina mountains. The area has lakes and cabins. Ashville is an excellent city. When you return SE, you are in the heart of the Carolina barbecue region.

Take care that your three weeks are not all windshield time. I recommend fewer miles and stops with more time to enjoy your destinations.

Was born in the Big Easy live on the Gulf Coast AL/FL border

avoid peak summer season chock a block shoulder seasons best

For me fly into neworleansonline.com carrentals.com out of MSY

classic.mapquest.com directions distances my route

to Baton/Rouge Lafayette for best Cajun Prejauns my fav

Natchez www.scenictrace.com to Nasheville/Chatanooga/Smokies

down to Atlanta Callaway Gardens down to seasidefl.com

sandestin.com Pensacola orangebeach.com wolf-bay-lodge.com

great sweet shrimp Sonny's for BBQ Mobile Boloxi(casinos)

back in to neworleansonline.com

Keys a bridge too far away for me in the time you have

Happy Travels!

kpauls.com my fav in NO blackened redfish that will

melt in you mouth...

I'm not an expert on the south but I've travelled there several times over the years. I agree that you are trying to cover too many miles in 3 weeks. I visited my daughter several times when she was an undergrad at Emory, and we really enjoyed Atlanta. It has several very different neighborhoods, & fun & interesting sites that usually are not overly crowded, except for the aquarium. Also visited friends who have a cabin on Trey Mountain in Helen, GA. That's a nice area,too, with lakes & mountains & forests. Savannah & Charleston are beautiful small cities. I like vacations with a mix of cities & small towns & countryside. Both of my daughters (who are very well traveled) have been to Asheville, NC, & they say it is one of the most beautiful places they have seen.

Because the Florida Keys are so far away from your other destinations, would you consider the Outer Banks in NC for beach time?

"Which essential places are we leaving out? What's not really necessary?" Skip Jacksonville and substitute St. Augustine.

"Keys a bridge too far away for me in the time you have" Agree. It's too far, out of the way.

_____________________________________________
Vic's travels: http://my.flightmemory.com/vogilvie

One more suggestion: if you decide to visit both Asheville & the Outer Banks, it's about an 8-hour drive from one end of NC to the other (I think). You could stop mid-way in Chapel Hill & Carborro. Both are small towns, very pretty, & Carborro is more artsy. My other daughter went to grad school at UNC so we visited her several times & enjoyed the area. If you like wineries, the Haw River Winery Trail is nearby, too. We visited several wineries, one of which is in Mebane.

First, charleston is in SC. You need days there to eat "right".
I HIGHLY recommend a trip through Birmingham Al (on your way to Atlanta, if you must) and eat at Frank Stitt's Highlands Grill. Truly SPECIAL.
The Outer Banks is a LONG LONG way from Asheville. And the Keys are a LONG way from a lot of places!
I think you have a bit too much even for 3 weeks.
Recommend you get Guy Fieri's Diners Driveins and Dives for ideas of cute places.
ALSO John T. Edge's book Southern Belly for super ideas of OLD places. He is the executive of the Southern Folkways, an organization to preserve southern food.

While you're on the gulf coast, I recommend a visit to Apalachicola. Quaint historic town with a nice vibe. Wonderful seafood, no crowds. The Historic Gibson Inn is one place to stay, there are several B&Bs in the area, or you could stay on St. George Island (a Florida beach with no high rises and no commercialism).

Didn't read anything above that I don't agree with.
Since you are renting a car anyway, You should get a cheap flight to Atlanta and rent and return the car there.
Anything south of Miami is probably too far to go.
For an adventure on the way home to NYC you could ride the Amtrak Crescent from Atlanta to Washington DC to NYC.

I realize the Outer Banks is far from Asheville. I only suggested it if they do decide to go to Asheville, then they could go to Outer Banks before heading south to Charleston & Savannah, & then eliminate the Keys. All depends on their route & if they visit Asheville.

I agree with the above poster who recommended Apalachicola Florida. It's a quaint little town to walk around but I would recommend that you stay on the ocean. This b&b would be about 20 min from Apalachicola in Indian Pass. It has been recommended here before and would be on your way to New Orleans: http://www.turtlebeachinn.com/ While staying there drive nearby and visit Cape San Blas...beautiful, beautiful beaches and a State Park on the peninsula. If interested in this area, I can recommend places to eat.

Guys, thanks so much for all the suggestions.
We're eliminating Florida and I'm making a list of all the foodie recommendations you noted. Also, adding in the new towns you wrote about.
A follow up question -
Do you think it makes more sense to fly into Atlanta, rent a car there and then make a loop encompassing most of the places mentioned above ex-Florida (ie NC, down the coast to Savannah, then Alabama, Louisiana, and up again to Atlanta) OR to fly into New Orleans, rent a car and then head to Alabama, Georgia etc ending up in Atlanta (we want to visit friends there) and returning the car there?
Also, Dauphin Island and Gulf Shores park... worth a visit or not so much?

PS: I think we're gonna add Apalachicola to the itinerary given high ratings and Asheville sounds very very tempting... so much space to cover and not enough time!

What time of year is this going to take place?
Personally I would divide your actual time (about 19 days) and look at a map and see what is going to maximize your trip stops. The Outer Banks took a HUGE hit with the hurricane. It is hard to get there by ferry, plus the actual distance to cover. I don't know how things are really progressing with services there.
Asheville is a cute town. It is basically a bit north of the other many places you have listed. I would keep the loop south of Atlanta, even with eliminating Florida. Along the southeast coast--Charleston to Savannah--there is quite a lot. Along the gulf coast there is quite a lot. NOLA deserves several days, as does Charleston. Subract those days, and then see what you have. Just a thought.

How about a beach in the panhandle of Florida? I don't know much about Gulf Shores AL.
I suggested flying to Atlanta because of the cheap flights. It should cost less to rent a car there if you consider that you might pay a one way rental fee if you rent in NO and return elsewhere.
You can easily drive from Atlanta to New Orleans in 2 days at a leisurely pace.
A night in one or the recently rebuilt casino/hotels in Biloxi would be nice even if you don't gamble.
You can see the OBX on a future shorter trip from NYC.

We're going this December(in a week)... very last minute planning.
We're basically hoping to avoid booking all lodging in advance and just stay in motels along the way.

A drive from Atlanta to Cape San Blas/Indian Pass/Apalachicola Florida is only about 7hrs and you can enjoy the ocean/beach for a day or two. You can then take 30a to 98 going thru Port St Joe and on to Panama City This is a nice drive along the ocean, you can then drive on to Pensacola and more beach if you so desire. On to New Orleans about a 10hr drive from Indian Pass to NO.

So you haven't made reservations yet? Brave souls. Do you have a GPS/Ipad? Could be very helpful.
So beach time except for nice walking isn't going to be an activity.
YOu can drive from Atlanta to NOLA in a day pretty easily too, depending on what the time "pressures" are.

Seems like the backroads and byways of South Louisiana fit your description perfectly -- you can fly into Neworleans.com and spend a few nights (it is possible to avoid the crowds/Bourbon Street b.s., catch some great live music, eat-eat-eat), then rent a car and drive to Cajun country for a taste of that quaint/local/authentic flavor you're looking for. The area around Lafayette and Breaux Bridge are excellent for exploring, and FILLED with exactly the kind of off-the-beaten-path food stops/culture you're looking for. Just a few recommendations to whet your appetite:

Cafe des Amis, Breaux Bridge (don't miss the gateau sirop cake)
Cochon Lafayette (new outpost of the New Orleans restaurant)
Best Stop in Scott, LA (for boudin)
A-Bears in Houma, LA (peanut butter pie)
Sportsman's Paradise in Chauvin/Cocodrie for the BEST seafood gumbo and friend speckled trout you'll ever have. The owner, Ms. Connie Townsend, is lovely!

Depending on the time of year you're here, you'll likely run into one of the countless food or music festivals.

The beauty of South Louisiana is that you'll NEVER run into the 'tourist hordes'. The people who do explore the area don't travel on buses or in packs -- they're independent travelers to like to strike out on their own and are comfortable finding their way around a new place. Another bonus: the culture (food, people, music, history, arts) is one of the most unique and unusual in our country. And, depending on who you ask, it's also a slowly disappearing culture -- the state of the coastline and wetlands and other factors are impacting the culture and, again, depending on who you ask, it might not be around for forever to experience.

Just my two cents...your list seems to cover a lot of major metro areas in the South, but to get the experience you're looking for, you've gotta get out of the city and into the 'sticks' to find it.

What time of year are we talking about here?

cd beat me to it on recommending Turtle Beach Inn. starrs has s TR that got me hooked on trying it out & it did not disappoint. I think I added my TR to hers.

I'm from the Dauphin Island/Gulf Shores area & Dauphin Island would definitely be considered 'back roads' in my book. It has a niche following, but not me. I much prefer Gulf Shores & if you're wanting some not quite so populated beach front, Gulf Shores can fit the bill - I personally love it.
There are old forts on both Dauphin Island & GS & a ferry that connects them if you like. Dauphin Island also has a Sea Lab that you may enjoy if you do decide on keeping it on the list.

I also recommend ' keeping it south of Atlanta ' for best use of your time - & no back tracking ATL to NO & back imo.

I'm wondering if Jacksonville is on anyone's must-see list. Culturally, once you get a bit south of Jacksonville (the largest city in South Georgia, according to one friend), you're out of the South and into "Florida" which is a separate cultural phenomenon.

Gulfport and/or Biloxi are probably worth a visit and you can cut an Alabama destination.

And if you really want good food, stop by Jacob's Andouille in LaPlace, LA just outside of New Orleans (on the Airport road).

Apalachicola/St. George Island/ Cape San Blas, Florida, that area is a great choice for beach time.

If you are stopping overnight in Alabama, I would avoid the immediate west side of Birmingham, say from Hoover or downtown over to Bessemer. Tuscaloosa is fine - if you are into football the Paul "Bear" Bryant Museum is at the University of Alabama.

Places to eat there - Archibald's Ribs - a hole in the wall place, has probably the best ribs there. Downtown, DePalma's on 15th street, has great food, especially the White Chocolate Bread Pudding.

City Cafe, in downtown Northport (just another part of Tuscaloosa) is popular because they have a great "Meat and 3".

North Alabama - Scottsboro has "Unclaimed Baggage" a store filled with everything lost in shipping or with an airline. I bought a great lens there once. Don't go on Saturday.

The Mentone area has Little River Canyon - the deepest canyon east of the Mississippi. DeSoto Falls is there. It's a quirky little town on top of Lookout Mountain with craft shops and a few B&B's.

Gorham's Bluff is across the valley on Sand Mountain. (Sand Mountain has been featured on the Travel Channel, I think, as the home of snake handlers, although I don't think I've ever met one, and I have a house up there.) If you want a real break from hurry/worry, stop at Gorham's Bluff. They have a Lodge, there, and some rental cottages, and there's one cottage listed on VRBO.

FYI, if you were going northwest from Atlanta, you would reach Mentone first, then down the mountain and cross I 59, go west up on Sand Mountain, pass through Pisgah, where Gorham's Bluff is located, then continue down off Sand Mountain past the Guntersville Lake area, into Scottsboro. Huntsville is past that going toward I-65. I-65 runs through Birmingham, as does I-59.

Hope you enjoy your travels

I would avoid Montgomery, if you are planning a stop over.

There's always the Space and Rocket Center in Huntsville.

Alabama has a lot to offer, rivers, mountains, lakes, beaches, museums.