My standard three battle pets by default are:
Iron Starlette
Ethereal Soul Trader
Mechanical Pandaren Dragonling
That setup beats most pet battles, although I sometimes have to rearrange them (e.g., that setup above works for the DMF pet battle guy on the left, and I switch the order of the first two for the pet battle guy on the right).
But there are exceptions. In the garrison, the King and Queen florets really require one or two max level calfs (e.g., the meadowstomper stomper type calves). And there’s one pet battle in Tirisgarde (the chitten one Chitarra?) that requires one of those moths with the moth ball attack (5 attacks per turn).
Other good all around pets are the Anubisath Idol and the Emerald Whelpling (or any similar ones with good heals) and the Magical Crawdad, also the gnome one from archaeology.
I’d suggest, if you have higher level alts, to take advantage of the garrison pet menagerie building, since that quest chain gives you that item that makes any pet level 25. If you do that on a few alts, you can start to quickly build up more level 25 pets.
Also, keep an eye out for Squirt in the pet menagerie and read the guides to use her to level up pets to round out your team.
When Squirt is up in the garrison during a pet battle bonus event, that’s when you can level up pets even faster.
Note that there are pet battle items that increase the XP your pets get, so that can help out with leveling.
But generally, just go out into the world and capture pets in BfA, Legion, and WoD, which will all be level 22 or so when captured, so you can quickly get them to max level to try and have a stable of them to use for special situations. I’d recommend using a non-max level toon to capture those pets, so you can benefit from the XP gains, too, to your toons.
/moo