Flying is a game-changing ability.
Game-changers are abilities that drastically expand the character's capabilities, often allowing them to bypass certain types of obstacles completely, like walls, cliffs, traps, and even melee encounters. These are described in the Gamemastery Guide (page 46):
As you can see, some of them can be obtained earlier than the others, or might not even show up at the table at all. But whenever one of those abilities start to show up constantly, the GM has to be prepared for them. Since our concern on this answer is Flying, here is what Paizo developers said about it in the book:
Flying: Your immediate concerns are more tactical when flying shows up at your table—do melee-only monsters get slaughtered like bison on the Great Plains? You’ll need to consider the monster mix in your encounters more carefully so that the players don’t just fly above the dire wolves and drop rocks on them. But there’s nothing wrong with letting the aerial advantage be an advantage every once in a while. Let the flying PC trivialize an encounter or a trap—there are always more of both coming down the line.
Unlike most other game-changing powers, flying comes with a hidden danger to players: altitude. When a ground-bound player gets stunned, knocked out, or
dropped to negative hit points, he slumps to the ground. Depending on the exact nature of the flight power, the consequences for a flying character might be far more severe. If a character runs out of hit points and can’t fly anymore, impact with the ground will almost certainly finish him off.
When a player learns to fly, it’s worth a brief conversation with that player. Show him the math: “If you reach 0 hit points when you’re x feet in the air, you’ll take y damage on average, which leaves you at negative z hit points—dead, in other words.” Once he’s got a grasp on the inherent danger, the player can take calculated risks, and it adds even more drama to a desperate battle in the sky.
You can fly at first level
All that said, do note that flying can be obtained as soon as first level, as there are three playable races with flying speed: Strix (black-winged flying men), Gathlain (flying plant fey) and Wyvaran (flying humanoid lizards).
Being tied to races, they are both great advantages and come with some disadvantages. You can't hide that ability, and you can't choose something else instead of that ability (like an extra feat), your character can fly and everybody knows that. There are exceptions to this, like Gathlain's Sticky Tendrils, but they replace their fly speed by the ability to spider walk and glide. However, they keep all tactical advantages described by the developers.
Its worth noting that small-sized druids and hunters can take medium-sized animal companions, which they could ride starting at first level. A Roc (12 str, light load 43 lbs) or Bustard (13 str, light load 50 lbs) companion are not strong enough to lift most small-sized characters and their gear, but it's not impossible once you consider options like Ant Haul. A naked female gnome weights 32 lbs, while a female halfling weights 27 lbs, and are probably the two best options for this. Also, goblins weight the same as halflings, if you ever consider playing one.