Tell me I'm nuts, but I think Levitate should be a factor instead of an ability. That way, Pokémon that can canonically float and/or fly will have the ability to do so (Example - Jellicent & Garchomp), and many Pokémon that the Flying type was slapped into will finally be free of its odd type. Gyarados can be Water-Dragon, Gliscor can be Ground/Poison... So many possibilities! Not to include that since Levitate would no longer be an ability, Pokémon could have another ability. Tinted Lens Flygon, Drizzle Bronzong, Magic Guard Claydol, Speed Boost Vikavolt (that and a stat change; weirdly enough a Pokémon who the Pokédex states to zip through the world is slower than Grubbin), Moxie Hydreigon...The Flying type for Gyarados feels really awkward, when 1) Mega Gyarados is Water/Dark and 2) it feels like Water/Dragon.
In fact, the Flying type is rather poorly implemented, because several Pokémon feel like they should be Flying, but at the same time, they have to represent 2 other types, and they cannot have Levitate on top of that.
It's almost like the series need ANOTHER "stat", based on whether the Pokémon is more on Land, Sea or Air, each with their own Rock/Paper/Scissor strenghts and weaknesses.
While I told all the good sides about this factor, there is also some downsides. The Ground-Type Pokémon get severely nerfed, since it can no longer spam STAB Earthquake in mostly anything since 200+ (and maybe 250+) Pokémon would be immune to it. This crisis could be easily averted by giving Ground-Type another advantage; an immunity. But to what? Poison or Rock are my best bets. Although having two immunities can seem OP, but the Ghost-Type has two and no one complains about it. Fairy-Type needs to be surpassed from the "Most OP Type" title eitherway...