I think it's a close call at any level.
If we assume an evil cleric, then a properly equipped Paladin might be able to kill him with one lance charge at mid and higher levels.
Let's see:
Assume an 18 Cha and 14 Str, 9th level human paladin, +2 lance
Spells Cast: Divine Favor (+2 Atk and Dam); Righteous Fury (+ 4d4 temp hit pts, +2 AC, +2 STR and DEX, +2 Fort)
Rhino Hide (on the horse and rider, if you must - some combination should work without any arguments), Spirited Charge, Divine Might and Smite Evil. Pretty standard fare for a paladin.
Other items should probably be geared toward helping saves - especially Will save)
To hit: +9 (Pal), +4 (Smite), +2 (Str) +2 (lance) +2 (Divine Favor) + 1 (Righteous Fury Str Enhancement) +4 (Smite) = +24
Damage = d8 +2 (Lance) +2 (Str) +2 (Divine Favor) +1 (Righteous Fury) +9 (Smite) = d8 +16
Multiplier = x2 (charge) x2 (Spirited Charge) x2 (Rhino Hide) = x4
Damage total = 4d8 + 64, average = 82
Average hit points for cleric (12 Con) = 76 + 9 = 85
Whew - close - plus a Fort save or die from massive damage.
Who wins? A close call for sure. First intiative and clerical domain spells will go a long way toward deciding the outcome.