Me and my wife are leveling 5 Characters on a European PVP Server,
Wife: Warrior and Priest
Me: 3 Locks

They are about 35 at the moment. its fun

My wife wants to also try 3 Mages... What would be a good compliment to add as 2 additional classes? Paladin, Shaman or Shaman, Druid or what?

We like doing instances, probably later some BGs and open world PVP of course and at a later stage (70) 5 man heroics...

Thanks for the Help.