I love Key West- but I think its somewhere you have to want to go..
Charleston and Savannah are VERY romantic- as most of us know. I personally vote for that.
If you are going during a hotter month, Destin, Florida has nice white sandy beaches and are, in my opinion, one of the nicer class beaches.
I would make this entire experience a Disney experience. Check out the cruise!!
Whatever you decide goodluck!!