4 mages, all fire, all frost, or a mix?

[Ethario]

Frost is better DPS than fire until you get BWL+ level gear. Also much more survivable with ice block, ice barrier, cold snap, etc. Fire also goes OOM pretty fast without enough crit.

I recall watching a video of a guy boxing all mages to clear Strath UD a long time ago. On a private server, though.
https://www.youtube.com/watch?v=RaolIYYAI5M

Prot/holy allows you to either tank or heal. You can't do both at the same time. You'll need a tank, healer and 3 mages in order to do dungeons.

My current best team for dungeons is actually 4 hunters and a priest

[Apatheist]

My current best team for dungeons is actually 4 hunters and a priest

I've done the same thing with warlocks but mages don't have pets.

If he plans to play the paladin as a tank he'll need a healer.