Actually, my friend loves the Paladin, and he uses it to terrifying effect. Imagine 12 Militia, 12 Footmen, an Arch-Mage and a Paladin establishing two sub-bases
before the second day dawns.
Needless to say... it was KO for his opponents because they simply could not keep up with his unit production. Remember... the Paladin boosts the men around him( Devotion Aura), so when you have a swarm( or play in teams), it is a very good idea to have him around. Not to mention that he is virtually impossible to kill( Divine Shield).
The Mountain King has his uses, and he is
the Anti-Hero Hero, but do not knock off the Paladin so soon.
As for box-art, it definitely has to be the Night Elves.