Disclaimer: I don't do much PvP so my suggestions aren't very helpful if that's what you're looking for.
Unless you're a Gotta-Catch-'em-All sort of pet collector and want everything Rare, I'd avoid the cheap and common pets like cats, moths, snakes, dragonhawks, rabbits, etc. Generally the pets that are harder to get hold of are also more powerful and more useful.
Feline Familiar (there's only 1 breed) is my very favorite teammate when I'm working on leveling lowbie pets.
Gilnean Raven is invaluable with a couple of the master trainers.
If you torture yourself doing the Celestial Tournament, Curious Wolvar Pup, Mechanical Pandaren Dragonling, Ghostly Skull, Lil' Bling, Macabre Marionette are super helpful against certain opponents.
Sea Pony, Death Adder, Jade Crane Chick, and Enchanted Broom are good to have in your stable.
Normally I refuse to battle stone a wild pet that I could capture Rare even if it takes a while. I've made a couple of exceptions, pets like Minfernal and Giraffe Calf where it's so hard to find one of any rarity.
I notice that ultra-helpful list of Uncommon-Only pets mentions that you could battle stone the pets like kites that can't battle. Personally I can't imagine why you'd want to do that, seems a bit extreme.