A paladin has some perks that may not shine in every campaign, but are very important in some. The immunity to fear and disease is very nice when you face foes that use such attacks, especially undead. Turn undead can also be a very efficient power when faced with things like shadows that can wreak havoc on PCs. The charisma bonus to all saves is an immense boost. With a high charisma a paladin wlaks through spells that best the rest. Even a clumsy paladin (dex 8) has a decent reflex save thanks to her Charisma, which many a fighter cannot match. Then there is the lay on hands ability. Not only is it the most efficient healing - you do not waste a single point - it also makes for good offense against undead. Let's see how that Lich likes it if you pour the whole amount of the lay on hands healing ability into it as damage. Smite Evil is also a perk of the class, since it allows the player to decide when to do more damage instead of waiting for a critical, or sacrificing attack for damage with power attack. As long as you do not fight that many encounters per day a paladin can really dish it out against, evil and undead by choosing how and when you use your abilities.
Now comes the mount. Don't think of it just as free transport, consider it a big familiar. It is intelligent, gains useful powers (ever thought about how the command horses power can be used against opponents in a charge?) and not too shabby in a fight by itself, not to mention when used with a heavy lance and spirited charge. Remember Fury? A paladin mount is just like Fury, and who would not like that horse on his side?
Now add in spells. Create water may not seem like much, but travel through a desert and it is a godsend. Bless weapon has been mentioned before, a real boost even if you have a magic weapon already. If you use the splatbooks there are even more spells, some specifically made to let the paladin reach that BBEG through his horde of followers, but one in particular stands out, the nice spell that lets a paladin sacrifice up to 10 hitpoints for 5d6 additional damage (Divine Sacrifice iirc).
If your battles are one like the other all day long, then a paladin may not shine as much, but if you happen to regulrly have climatic battles against a big evil thing, then a paladin, unlike a fighter, can really focus on that encounter with spells and abilities and dish out a ton of damage in one blow.
That was the mechanic aspect, now for the roleplaying advantages. A paladin is more than just a mounted fighter, or even a shining knight - he is a warrior chosen by a god himself. Almost anyone has heard stories about paladins, and their code. In a feudal system a paladin embodies the legendary chivalry of the knights of the round table, and the might of the church and at the same time has the thrust of the common people. Paladins are rare as well - your paladin will be one of a few chosen, recognized for his valor and honor by strangers, foes and friends alike. You may not be that good at infiltrating the evil hideout, but few manage impress people like a paladin, and he does not even need to drag a dead dragon behind him. A paladin can also be trusted, and people in power know about his code. That means that any attempt to frame him for a crime has less chance to succeed than it would have when the target was a valiant but violent fighter.
Paladins are also noble by default, which is a very important perk in a feudal society.
Last but not least, while the church may order a paladin around (also known as "convenient source of adventure hooks" by DMs), the church also offers a vast amount of ressources to a paladin, who is, after all, one of the "stars" of the organization, chosen by the big boss (i.e. god) himself). Mess with the paladin, and you mess with a whole lot of clerics.
Edit: forgot a very valuable spell. Just for information: I do not play a paladin, but I DM for one, and so I have experienced all that I mentioned.
