Nice if you could add it to the OP
I was thinking it would not be like regular Air Unit (based in a city) but more like the Helicopter unit. Perhaps Balloons could be upgraded to Helicopters eventually. As they would became available quite early (by Physics).
"Ranged Combat only (Cannot be melee attacked by enemy units), Ranged strength 5."
This was the Balloon combat ability idea by me and Pouakai in his compilation thread. Yes, melee units cannot attack them but can enter the tile because Balloons 100% retreat chance when attacked by melee units (love your idea).
I like this idea as well. They could explore quite far away from your empire if based in allied city state cities. Though this would require that you would have quite many of them to get a far. Kind of like step by step. Recon Run is a nice idea.
I was thinking the Great Explorer improvement would be the Cartographer building (list of cartographers), for example. Will have to think about the tile Yields. Perhaps giving small amount of gold, science and generating Exploration points (which would count for new GEX to born). Perhaps it could have alot of movement, large sight radius, a high retreat chance, double yields from ancient ruins, finding natural wonders and pillaging barbarian camps. Also giving +1 line of sight to frindly units in adjacent tiles...
Hmmm... I'm not really convinced about the GEX. It seems like taking it a bit too far. It's never going to be as usefull as the other GP I think. Exploration is most important early on, while GP usually come a bit later. Perhaps the improvement could have a very large sight radius of it's own, so you can use it to see deep into enemy territory.
As for the balloon. I like both ideas equally, but I'm going for the citybased one, otherwise it's too much a competition with explorers. This way they both have their own distinct way of exploring.