I have now verified that hunter/paladin is by far the best pair of classes to level together using Recruit-A-Friend.
Having gotten my copy of BC and upgrading the trial account fully, I created The Sisters Bulimia (female blood elf hunter and paladin) and plowed through the well-designed BE starting areas. The ludicrous xp inflation was still in effect, and over that first weekend I plowed through 30 levels with only a few hours played per day. Halloween was going on, so every inn offered a nice chunk of free xp, along with a one-time easy boost from putting out the fires the Headless Horseman liked to set in the lowbie towns. I didn't waste any time with professions, except on First Aid for the hunter, who was on my original account and would be doing the vast majority of the fighting.
I found that the biggest stumbling block to leveling was the class quests. The hunter had a lengthly quest line to learn to tame beasts. None of that quest xp went the the paladin, creating a deficit until I did her class quests to learn the resurrection spell. I basically got half the xp for my time doing these quests, but they were necessary to keep leveling.
Hunters were changed drastically in patch 3.02. I'm somewhat notorious for leveling hunters and never finishing them (have one parked at 43, one alliance at 60, and numerous hunters in their 20s), ever since vanilla WoW, so I'm pretty familiar with the torture that was learning pet skills. Clunkily, you had to leave your pet in the stable, venture out to a dangerous area without the pet, tame the right new pet who already had the skill rank you needed, then use that pet to fight until you learned the skill from them. You had to do this for every rank of every skill you wanted the pet to learn. It was needlessly punishing.
Blizzard took it all the way back in the other direction. When you tame a new pet, they come equipped with every non-talented skill that they will ever have (a focus dump, a racial skill or two, and growl), and those skills level up automatically with the pet. That's what's known in the business as a substantial improvement. This made leveling quite a bit less painful. Pets have also been divided into 3 groups, representing dps, tanking, or utility, each with their own pet talent trees full of new and old stuff. Wanting to level super-fast, I picked up the most immediately available dps pet (a lynx), who came equipped with like 5 skills that I would never have to put any work into upgrading.
Since I would be leveling quite fast and not necessarily updating my gear (upon reaching level 60 my Paladin was wearing mostly level 30 gear, for instance), I went with the least gear-reliant spec for the hunter: Beast Mastery. Let the pet do all the work: and work it would. Most of the time I could get off 2 shots at best before the pet had decimated my target. I was mowing things down. Nothing could kill like the hunter while leveling, making it the best dpser for a RAF pair.
This was helped by bringing along the best passive buffer (and therefore absolute best second character for an RAF pair), a paladin. I specced the paladin deep Ret. This had a few minor advantages, like buffing Blessing of Might (on the hunter and pet at all times) and increasing riding/running speed (the hunter took the mount speed talent in BM as well). But it had one major advantage: the newly consolidated Retribution Aura.
Back before the patch, all paladins had a basic Retribution Aura that simple reflected a small amount of holy damage whenever a party member was struck. They also had another aura that increased Holy damage, but could be talented to increase all damage by the party by 2%. Now, those two auras are consolidated, and at least 3 sets of talents in the Ret tree buff the new Retribution aura. So by keeping it up all the time, I buffed my pet's damage by 2% as well as causing him to reflect holy damage on attackers (which made it possible for the pet to hold aggro on multiple targets without attacking them all actively) and later increased the group's haste by 3%. So my hunter and pet were basically walking around with Blessing of Might, reflected holy damage, and a 5% damage increase just for having the paladin tagging along. Add in the fact that the Paladin could heal in a pinch and even bubble and run away from a lost battle to prevent a corpse run for the dead hunter, and you had a winning RAF recipe.
Clearly, by far the best possible pairing.
Oh, and by the way: level 1-59 in about a week, playing only 2-3 hours a day on average. Booyah.