It would be like the Ultimate planet destroying ships you get in Gal Civ 2, Doom Stars I think they're called. End Game units of course.
Bad example there. No matter how much I love Gal Civ II, the Terror Star (was that the name?) was bad bad bad bad bad bad bad. With just 1 point of movement, I'd only build one for the fun of doing it. I have never blown up a sun yet and surely will never do it.
Different planes would be a very good idea. But as everything, only if well done. One mod I have in mind would need 5 different planes to be considered complete (can survive with just 1 tough). But Frogboy already said something about land based TBS so doubtfull unless very good arguments against that are given (and money and time allow, of course).
And aerial plane could be a nice addition for flying things but I'm not sure it's really needed. In the 3d engine you would see them lying normally in the map and in the cloth map, it would be just a figurine lying of the surface of the map.
Undersea map it's more interesting and problematic. In the cloth map the figurine would behave like any other (over the cloth map) but in 3d game it would depend. A sunken city would be underwater and you should be able to notice it without the need of cloth map. A giant turtle could be in the surface but could interact with the sunken city if in range.
Different worlds (underworlds included) would be nice if you already have an interesting world and if you can make the new ones interesting too.
But the topic was about flying cities (I prefer sunken ones) so let the flying citadel detroy the area where it was before (at least forsaken or something). The cost could be mantained but it would be cool if the cost could be paid once and the effects sustained by itself (once magic skill is good enough). I can see people using "It's raining flying citadels" tactics if the game allows them. Maybe to make it fly it's a one time payment but o make it move requires extra effort (be it essence and/or mana, preferably the later).