If a paladin lies to the goblin boss, who cares?
Me. Lancelot and Galahad and Arthur are honourable. That their foes are dishonourable, incapable of conducting themselves in a fitting way is a burden on those foes, not on them. They won't sully themsleves with lies and deception, however base those with whom they must deal!
The Paladin is a force for beneficial civilization. If the paladin does something evil, which really is usually pretty obvious, he is not supporting the benefit.
I also hated chaotic stupid, and think Batman should have killed Joker a long time ago. How many have died because Superman refuses to kill the evil-doers?
Thus do I prove that it's often not very obvious at all!
Paladins aren't necessarily knight-themed in 3rd and 4th edition.
I don't know 3E well enough, but a 4e paladin wears Full Plate, typically carries a shield, and is a selfless defender who specialises in interposing him-/herself between enemies and allies. In the Essentials version she is dedicated either to Virtue (like a knigh) or to Vice (a black knight).
There's no steed in 4e, true, but that's a function of the fact that (i) it doesn't care much for pets, and (ii) like many fantasy RPGs, it's mounted combat rules aren't all that smooth.
I guess you could do funky stuff with a hybrid who didn't take Paladin Armour Proficiency, but that's a bit of a corner case.
This right here... without the code I'm finding it hard to discern the difference between a cleric (martial champion of their deity) or cleric/fighter and a paladin (uhm... more martial champion of their deity???).
There's never been any difference, other than the mechanical. Clerics are modelled on crusader knights. Paladins are, virtually by definition, crusading knights. It's the same thing.
Of course, you can amp up the behavioural restrictions around the paladin if you want, but that is just another mechanical difference. Do we really think that Edward the Confessor, or Roland, or Aragorn, took his obligations to god more seriously than did the prophets on whom many of the more iconic cleric spells are modelled, or than the Knights Templar who are said by Gygax to be their archetypical inspiration?