New to multi-boxing - best healer to pair with Mage?

[nodoze]

if you think one step further I would suggest a Paladin [+Mage] ...

I agree. In addition I think one of the duos often recommended for new players is Warlock+Paladin as it allows the Warlock's void to tank better (due to salvation+sanctuary+retribution) and survive past it's normal limits (with buff/mitigation/healing from Paladin) and both get free mounts.

Mage can also be somewhat synergistic but often the things a single mage can pull off (more than any other class) require the mage to be very mobile and that movement isn't very conducive to multiboxing and can be especially problematic to a healer like a Paladin that is mainly stationary when healing.

Thankfully a Paladin can be a strong healer and tank from a single spec and can open up some AoE scenarios that don't rely on movement. With aggro management a Paladin can AoE Tank without all the movement and the Mage (or Warlock) help AoE kill things much faster than the single Paladin can AoE alone. That can be fine if you want to tank & spank AoE grind in a more relaxed fashion but I don't think you will be beating the crazy AoE scenarios a single very mobile mage with strong twitch reflexes can pull off (like basically pulling/soloing most of Maraudon).