Well I figure that it all stands and falls with the factor speed, if Pterosaurs and Megaras get to fast there certainly will be problems.
An approach that came to my mind was that you could have an "Air Map", spanning over wider regions with lower ground detail, however this would seperate air from ground, making "flight shows" or simple "scouting ahead" impossible. If you ever played Seiken Densetsu 3 (To the point where you get the flamie drum) you will know what I mean with Air Maps