I had to practically drag my husband to Savannah, but once we were there, he begged to stay longer. We absolutely loved it. There are lovely B&Bs in “Old Savannah,” which would be great, but if you must be super-frugal, stay in a chain hotel outside of the older part of the city. Just make sure it has a shuttle. Most of the chains have free shuttles into the scenic part of Savannah. If you’re into forts (my husband loves them), there’s a very cool one on the way to Tybee Island, not far outside Savannah.
Speaking of Tybee Island, it’s great if you want to be on the beach, and you could drive in to Savannah for the day very easily. We had the most fun in Savannah just wandering aimlessly around the squares and poking our heads in whatever interesting attractions we saw along the way. Lovely. We can’t wait to go back.
I vote for the FL Keys- the weather is gorgeous, there are inexpensive things galore to do, fun places to go, actitivies, nature, happy hour, sunsets. I’m not sure about lodging costs, but you may find some bargains around Islamorada at some of the mom and pop places.
If Charleston, SC is still under consideration, let me recommend Middleton Place.
We stayed there a couple of years ago and really enjoyed it. It is outside the city, but close enough that you can easily drive in for meals, historic sights, etc. It manages to be romantic, elegant, and close to nature all at once.