The most fun I had leveling was with my Hunter/Priest combo. Back before they nerfed outdoor elites and group quests, I was able to do every non-instance quest at or below suggested level, which seemed pretty powerful at the time. I could also farm anything with no downtime and even got pretty good at instance runs, as long as I was a couple levels higher than the final boss.

Hunter/Mage and Rogue/Druid were also fun combos, but I missed the particular synergies I got with that original grouping.