I can understand the weather! We been asked to relocate several times. Here is a list of GT requirements by state.
http://www.davidsongifted.org/db/StatePolicy.aspx

Only 6 are require GT and funding it. North Carolina is one of them, and it's on the chopping block there. I would really look into the politics going on. Many states have education funding on the chopping block and GT is often first to get axed. It would terrible to relocate only to have the funding pulled soon after you get there.
We have refused to relocate 4 times in the last 8 years because of the GT programs. We have a wonderful school situation and have not been able to find replacements in new locations. Many schools have told us they have a program. It's often a pull out 1-3 times a week or just very minimal. We just haven't been able to find a replacement. I would really dig deeply into what they say is offered. Of course, we are not looking at any locations, but specific to where DH's company is located. We have live in 4 states and our current location is by far the best we've experienced. I know there are things out there and I'm sure others can help you find them in the warm and sunny places;)

The age can be tough. Many schools don't really do GT until older ages. They are focused on the social and emotional skills for the first couple of years. They also seem to want to wait to weed through the high achievers vs GT. It's frustrating when you have the GT kid. I know a lot people thought I must have sat in front of my DS with flashcards from birth. I didn't do any of that with him. He was reading at a 4th grade level at 4. Like flashcards or coaching him would have accomplished that! The right school will definitely recognize the difference between coached and GT.

Good Luck with your search. I miss my warm and sunny locations, sigh