To be honest, pretty much anything will be ridiculously fast. Remember that quests are designed to be easy with 1 person, so 3 people will just blaze through anything.

Personally, though, I'd go with the mages - teleport will let you get around really fast when you get to the point where you have quests that span both continents.