This list will be split into functional (the pets I think every pet battler should have) and aesthetic (the pets that pair well, like bears with hunters, elementals matched to mages).
The most powerful and useful in general are:
Nexus Whelping (Lethal vs flying, has AoE and is generally strong)
Kun-Lai Runt (Strong pet, especially vs critters)
Terrible Turnip (for capturing without killing wild pets)
and, if you have it, Grommloc from Blizzcon 2014
Some trainer battles, noticeably for the Timeless Celestials pet battles achievement (Master of Masters), the toy Elekk achievement (an Awfully Big Adventure) and the Tiny Terrors of Tanaan require often very specific combinations of pet skills to accomplish, but in general, the few pets above will beat most teams. PvP battles are a different matter but it still holds true overall.
This list doesn’t cover the roughly 60 or more pets you’ll need for the above achievements but it does encompass nearly every pet I’m found to be be particularly grown in battles – wild, trainer and pvp.
Harpy Youngling (vs Aquatic)
Graves (powerful AoE attacks)
Crusher (generally tough and strong)
Unborn Val’kr (powerful vs humans)
Weebomination (Touch, decent AoE)
Mechanical Pandaren Dragonling (good avoidance and damage)
Bone Serpent (can be particularly strong, especially in pvp)
Iron Starlette (lethal 3 round attack)
Teroclaw Hatchling (hard to kill)
Death Adder Hatchling (blinds, poisons, dots)
Nordrassil Wisp (AoE plus blinds, strong vs flying)
Ruby Droplet (resilient, strong self healings and avoidance)
Fiendish Imp (forces pets to swap)
Mud Jumper (powerful vs undead, self healing)
Anubisath Idol (can be hard to kill. A favourite in pvp)
Direhorn(s)(Resilient hard hitters)
Emerald Proto-whelp (It’s healing abilities can make it pretty hard to kill)
Tranquil Mechanical Yeti (Powerful attacks)
Blossoming Ancient (Very strong healing, can be annoyingly hard to kill. (From store)
Last, but not least the terrible duo, Pandaran Water Spirit (Geyser plus Whirlpool) and Chrominius (Howl plus Surge Of Power) which can destroy most pets. Mostly used on Celestial and Tanaan legendary pets. Sometimes swapping in with a pet with Doom, like the Unborn Val’Kyr.
Pairing pets with owners
Anubisath Idol, Ethereal Soul-Trader and Gilnean Raven are good with most characters, as if the Treasure Goblin is you have it.
Spawn of G’nathus for their evil looking nature.
Near impossible to get now, but if you have, it goes without saying the Lurky, Murky and other Murloks for cuteness factor. Pygmy cow too, perhaps. Singing Flower is a winner too.
Crusher for miners or alts wielding a pickaxe transmog.
Sea Gull / Sandy Petrol / Rustberg Gull for fishing
Terrible Turnip for herbers
Lil’ Bad Wolf for Worgs
Blossoming Ancient (store), Teldrassil Sproutling, Ruby sapling or maybe Tiny Bog Beast for restoration druids.
Soul of the Forge for Blacksmiths and fire mages, Maybe Shamans too.
Unborn Val’kry for paladins, I think, unless your have Murkalot
Stinkrot for Deathknights. Grotesque and crawling claw, maybe.
Blackfuse bombling or Iron Starlette for engineers
Droplet of Y’shaarj for shadow priests. Syd the Squid and Restless Shadeling are options too.
Maybe a Fetish Shaman for shamans, if you have it. Living Sandling and Searing Scorchling fit well, Tiny Twister is worth consideration, or maybe Lumpy/Grinder/Pebble.
Pandaren Monk for monks (store)
Netherstorm or Viscidus Globule for alchemists
Servant of Demidos for shadow priests, warlocks or arcane mages, as a fit.
Hunter has too many to choose from, to match or compliment their pet, search through the beasts and see what’s closest. Animals aside, I recommend the Curious Wolvar Pup or Kun-Lai Runt as a hunter’s companion, or Grunty if you have him.
Arcane mages : Manafiends or Crawling Claw
Fire Mages : Fire Searing Scorchling
Frost Mages: Frost Puddle Terror, Water Waveling or perhaps Tainted Waveling
Warlock: Manafiends, Kirin Tor Familiar, Minfernal or Sister of Temptation, as suits.
If you have them, Grommloc, Murkalot for warriors
You might also be interested in the Top Twenty Pets on Warcraftpets.com, rated for battle and for appearance.