I agree that the tenacity pets are generally better to solo with, and at lower levels (have no idea what level you are), you can get away with bringing them to instances, since ferocity pets don't really
shine til higher levels when the beat'em talents become available.
Popular tenacity choices for leveling are...*drum roll*...
-
Bears: Swipe is an AoE that will help to keep mobs off of you and on your pet instead
-
Boars: At level 20, I believe, you can spec into Charge. Charge + Gore = double damage, and is great for building threat at the start of the fight, making it more difficult to peel the mob off of your pet and onto yourself.
Now for the ferocity pets. I tend to disagree with the current mindset of "wolf > every other pet in the game", but I'll list them anyway since like it or not, they're a popular choice.
-
Wolves: Yes, yes, we all know what they do. Buff the damage of the pet and hunter for 20 seconds on a 40 second cooldown. But really, at lower character and gear levels when your AP isn't that wonderful anyway, it's not going to make that much of a difference. I prefer a pet with a shorter CD at lower levels, something such as a.....
-
Cat: Rake will give you steady damage on a short cooldown, and the first hit out of prowl grants a 25% damage bonus. Pretty handy, no? Not to mention there are tons to choose from at a relatively low level.
-
Carrion Birds: One of my personal favorites. The AP reduction is really nice for minimizing some of the incoming damage, not to mention it's even useful in instances that a warrior doesn't feel like keeping up Demoralizing Shout.
-
Raptors: Kind of a WoW staple, since they've been around since the dawn of time. Their family ability isn't going to give you the steady damage of a cat, but if it procs, it's very nice indeed. Plenty of colors to choose from, too.
And now, for the cunning pets. The majority of these are utility pets. I go for the more damage-focused cunning pets, while other people swear by the utility-driven pets. It's all personal taste.
-
Dragonhawks: These are nice because the fire bypasses armor, doing more damage on enemies/bosses who tend to take less damage from physical hits. The fire breath looks pretty nifty, too.
-
Wind Serpents: Another personal favorite of mine. Like the dragonhawks above, they have magic-based damage which will bypass armor. And, they have a really awesome swimming animation. <3
-
Ravagers: A pet I've never tamed and likely never will, but many people love them for their stun ability. If you're BM and have intimidation, you can keep an enemy stunned for a few seconds, which can save your butt if things get hairy.
-
Bats: Basically the same as a ravager, but with a longer range. The tradeoff is that it's also on a longer cooldown. Again, not my personal favorite but a lot of people like them.
I won't list every single pet out there, these are just the ones that I tend to see more often and that have their uses while leveling/questing/instance-grinding.
The choice is ultimately up to you. You can easily get three stable slots fairly early on, so why not just try a few out and see which one works best for you?

Many people are often surprised at how well a certain pet fits them that they'd have never thought to tame before.
I wish you luck!!!