Shamans is where I'm leaning.

Basically here's what I see. I want to use my resto shaman as the healer, regardless of the group make up and the master character - so the total group will consist of 5 characters.

Benifits of 4 mages: Huge burst damage and concentrated AOE damage (arcane explosion)

Benifits of 4 hunters: Namely 4 pets - I think this would make leveling the characters easier - I also currently have a L72 hunter and L72 shaman (on seperate accounts, I currently dual box these) so I would only need to level 3 togather.

Benifits of 5 Shamans: Totems, decent burst damage. The main benifit that I can think of would be healing - through having a macro on each character, you can have one character togather another, target another, target another, ect and cast chain heal. Also with 5 shamans its harder to target specifically the healer since the resto shaman can cast chain lightenings as well.

Another option with the mages would be leveling a priest with them and using that as the healer instead of my shaman.

Choices, choices!