There are a ton of "what pet to level first" threads in the archive if you want specific pet recommendations.
If you are looking to level via wild pets, get a pet with beast type attacks (to kill the critters), a flyer (to kill aquatics), a magic (to kill flyers) and a mechanical (to kill the beasts). The particular pet is up to your choice of playstyle. I recommend hard hitters with heals and/or hard counters (both strong vs defense AND strong vs attacks). Those 4 will cover 90% of wild pets you encounter. A couple of self-healing tanks (like a crab, or an Emerald Whelpling, for instance) can make capture runs far more enjoyable. A good Food Coma pet is also great for catching any wild non-critter.
If you intend to level via trainers, there are hundreds of guides out there with specific teams (even down to the specific breed and move-by-move sequence to beat them). Rabbits, moths, snails, turtles, and frogs seem to come up in a vast majority of trainer battle recommendations. Also, a good howl bomb team goes a long, long, loooong way to reducing the need for further pets (pet with Doom (preferably undead) + Pandaren Water Spirit + Chrominius). Arguably the single most useful pet (taking into account how easy it is to acquire) is the Mechanical Pandaren Dragonling. You can rarely go wrong with these.
If you intend to level via PvP, you'll need a set team you simply have a better chance to win with than lose with. It sounds simplistic, but PvPers tend to be trollish and either run proven combos or 3-of-a-kinds that are hard to beat if you are not specifically expecting them. I'd recommend avoiding using PvP to level until you have a fully stocked stable and a lot of free time to invest (human-driven battles tend to take much longer than CPU-driven battles).
Congrats to breaking into the top 20!