I had a lot of fun with the warrior/priest combo (before switching to 5 boxing). For leveling, Fury or Arms will work for a warrior (its your preference), and a shadowpriests Vampiric Embrace usually heals enough while questing to keep the warrior up.

Priest has a resurrect, heals, does good damage.
Warrior can tank, good DPS, plate, etc.