I've been doing pet battles since the beginning. I was never a big collector before then, so obviously I had plenty to do just to get a decent collection together. Once the collection was ready, I moved on into leveling all of them. Again, it kept me busy for a loooong time. After I had enough pets leveled, I started on all the world tamers, which took ages before I found truly viable strategies to beat them. Then came the tournament, which gave me fits but was tons of fun.
Along the way, I also stepped into PvP, and in my opionon, THIS is where it's at. PvP is the part that is meant to keep us interested and involved. Some people don't like PvP in the regular game. It takes alot of skill, quick thinking, and fast fingers. For some people, that's just not the way they play, and so they avoid it. By default, I think a lot of people also assume that pet PvP is the same way, but it isn't. Pet PvP is more like a timed chess match. Sure you have to think it out, but you don't need lightning responses to win.
The daunting part for new players is that PvP pits them against those of us that have been at it for ages. We know what pets are gonna do. As soon as we see our opponent, we have some idea what to expect, and we game plan against it. New players don't have that advantage... and so they lose... a LOT... and then they come here, or to Wowhead looking for that unbeatable team. Well we all know the unbeatable team doesn't exist. We learn because we lose and adjust to our losses. We watch what others are doing.
In the end, I think the biggest problem for new players is the overabundance of info out there. In the old days, if we found a tough tamer (Major Payne anyone?), we had to figure it out for ourselves. We took our lumps, and kept plugging away until we had a solid strategy, and as an added bonus, we learned alot about our pets and abilities. Nowadays, people get stuck, run to wowhead for a solution, and then move on. They aren't actually taking the time to learn from their own mistakes. I don't have a problem with the recent XP nerf to garrison fights. In fact, I think they've done an excellent job lately at creating parity between pets. I don't see those crazy OP teams anymore like the DAH teams, or crow teams, or Fluxfire teams. I see a really nice mix in PvP. Bottom line, the longer it takes to level your pets, the more you're gonna learn. The more you learn, the better you can adjust to challenges. The better you become at adjusting, the better you're going to be in pet PvP, and that is the REAL challenge that doesn't get old.