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...
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.