Well, in certain mythologies, we have a few kind of fairies that don't necessarily fly, such as nymphs, satyrs, etc. Due to that, it kind of makes sense to not have all fairy-type Pokémon levitate. If all fairy Pokémon stayed off the ground, then that would've given them another immunity in addition to dragon. Wouldn't that have made them a little overpowered? xD"
In my opinion, the only thing that fairy-types need is a cute- or beautiful-looking appearance. Fairies are not meant to look like monsters, y'know? Those who look monstrous could be categorized as some other type, such as dark, normal, and ghost.