"Challenge" und "smite evil" sind natürlich ähnlich, aber smite evil ist weit mächtiger (Cha Bonus auf to hit, doppelter(!) Schaden im ersten Treffer gegen Drachen, Untoten und böse Externare, AC Bonus gegen das Ziel), dafür gehts natürlich nur gegen böse Gegner (was aber erfahrungsgemäß 80-90% sind).
Der Paladin ist außerdem ein Caster, weshalb er eine zusätzliche Ability (Cha) braucht, was aber durch den Bonus auf die saves (und den Angriffsbonus beim smiten) versüßt wird. Außerdem bietet sich bei PF ein Bogenschützen-Paladin an ("Archerdin"), was wenig ikonisch, aber sehr mächtig ist, dann kann man STÄ getrost auf 10 lassen und die Punkte in Cha pumpen (natürlich braucht man dann Dex - viel nimmt sich das also doch nicht).
Ich habe mir die Ordensfähigkeiten nicht im Detail angesehen, wenn die nicht außerordentlich mächtig sind, würde ich sagen, dass der Paladin auf jedenfall kampfstärker ist, vorausgesetzt das Ziel ist böser Gesinnung.
Dafür hat der Cavalier mehr Skillpunkte (immer nett, wenn man keinen reinen Haudrauf spielen möchte), und sein Hintergrund ist etwas flexibler / mehrdimensionaler.
Hintergrundstechnisch finde ich es kein Problem die beiden Klassen vom "Geschmack" her zu unterschieden - der Paladin ist ein heiliger, zaubermächtiger Krieger, rechtschaffen gut, mit seiner Gottheit verheiratet.
Der Cavalier ist mehr ein Fantasy-Ritter. Von Adel, Ehrenkodex, aber durchaus mit viel mehr Raum für charakterliche Eigenheiten und auch "grauere" Charakterzüge.