OK A few things. First of all, chances are good that even in Florida you're getting at least a partial winter blend. Refineries have to retool the factories to make winter blend, which is why gas prices go up in the Winter>Spring and MidFall>Winter transition periods. I know that right now my truck is running crappy probably because I got a tank full of summer blend and it got hella cold here again. Last time I checked Gas Stations do not have to tell you what kind of gas they have in the tanks, the only real requirements are the octane rating and what the excise tax rate is.
Secondly, as I understand it, the "A/C" (i assume you mean air compressor, and not air conditioner) kicks on in winter as an effort to reduce the moisture inside the vehicle. This will, of course, reduce fogging which is worse during the colder months. The idea of dry air is what the conditioner in air conditioner really refers to. Dry air feels cooler (eg. 90 degrees in Flagstaff compared to 90 degrees in New Orleans), and less likely to hold heat, thus making it easier to cool a vehicle in summer. Vice versa in the winter the dry are helps reduce fogging, but makes is slightly harder to heat efficently. My mom's 99 Mounty was doing this and they asked the Ford dealership and the tech said it was completely normal. My 01 Sport does it as well. I too wish it wouldn't seeing it sucks gas, but this of course is still tied to the research that says when driving faster than 50mph and the compressor (here meaning Air Conditioner) is on there is no statistically significant reduction in mpg. This has been studied several times, and if Im not mistaken reproduced on an episode of the Mythbusters using Expeditions.
If youre still having reduce mpg, I do what everyone else has said. Hit the plugs and wires first, then go from there.
