The best class to duo with a paladin?

[Lune]

The correct answer is enchanter, for many reasons. It is an extremely powerful class by itself and can simply 'carry' the noob paladin, but if the paladin is skilled it can also contribute to the duo with agro, heals, stun on charm breaks, etc. Ench adds much-needed DPS. Any duo like shaman/paladin or druid/paladin (where druid can't charm) which relies on the paladin's dps isn't even going to be in the same league as ench/paladin.

Like others have said, an important consideration is: Do you know how to play enchanter well? Because the ench in this combo has a lot of responsibility. Slow combined with clarity allows the paladin's sustain to keep himself alive in most content.

Druid followed by shaman are also good but in a much more limited way due to aforementioned dps limitations.