Two accounts, starting Horde from scratch, best duo combos....and go.

[nodoze]

Warlock/priest sounds pretty good as mentioned above. Bear + cat is good, too as you can stealth around/through some things to save time. Warrior + healer would be good as the only downtime is due to the healer's mana. Two warlocks would be pretty good as well as they won't have any downtime unless the pet dies.

Warlock+Paladin is one of the best for similar reasons, in part, like how a Paladin healer really helps Warrior Tanks (heals, ret-aura & sanctuary on the Void and salvation on the lock and paladin)... That and both getting free mounts helps if a first duo on a new server.

That being said Paladin+Warlock doesn't fit the OPs Horde focus and similarly, while 2 Warlocks & 2 Druids can indeed be good, they don't fit the OP's stated goal to end up with 1 of each class ASAP.

[timotheose]

Hunter/Druid ... by far the fastest leveling and fun to boot.

You can tank instances with Bear and when you go Feral and get +30% run speed on both toons it's awesome!