Why Paladin?

If someone asked me to bet on the class from Player's Handbook that most people would either love or hate, my money would be on the Paladin class. Most people have different feelings about it, but one thing is for sure: they are strong ones. Usually selected by new players, thinking that they will be able to play their dream-knight in shinning armor able to slay dragons, unfortunately they are usually left with a bitter disappointment. From a character optimization view, the class lacks potential. This guide is for those that want desperately to play a Paladin for their fluff, but also need a combat edge for their knightly adventures.

In this guide i will try to explore the paladins and provide as many information as possible on them. Note that i will not focus only on the player's handbook class only, but also on the variant paladins as well. As such, don't be surprised if some feats/classes/abilities that can be only obtained by non good or evil characters are suggested. 


Attributes:

Paladins usually act as the leader of a group and are able to cover the social role, with skills like diplomacy. They are able to minor buff party members with auras and other abilities and also receive some amount of damage. Paladins are usually melee characters, but as described above, they can assume additional secondary roles which makes them suffer from Multiple Attribute Dependence (MAD).

Strength: Paladins are usually melee characters. While this is not your first priority, a decent score (~14) will make you able to dish out some respectable damage, especially in the early levels. Remember to place at least a score of 13, so that you can at least acquire the Power Attack feat early on in your carrer. Later, with a stat boosting item you will be able to push this attribute to a higher comfort level.
Dexterity: If you choose this you must wear lighter armor and probably use ranged weapons. Aside from a few occasions, this is considered a dump stat, as you will most probably want to create the knightly image and use plate armor, which hinders your dexterity modifier.
Constitution: This is important to a paladin as to any other character. Due to your role in combat, you are definitely going to have to survive large amounts of punishment. Fortunately the paladin class has good fortitude saves and comes with a modest built-in healing special ability (lay on hands), but this is not an excuse to invest lower than 14 in this attribute.
Intelligence: This is a dump stat to paladins due to the fact that you, well, won't be able to dump other stats. Due to their low skill points per level, paladins can't load up on many skills. Also it doesn't have other uses, except from the (powerful!) Faerunian feat Sword of Arcane Order from Champions of Valor. However, this also means that you will be unable to take feats such as combat expertise, improved trip, etc. This is not necessarily a bad thing, as those abilities rarely tend to have synergy with the paladin class, but it does cut some options.
Wisdom: This is your casting stat, as well the key ability for many of your skills. You can't dump this. Actually, even though this is your main casting statistic, it is debatable whether you actually need it to be high; this is because if you choose to multiclass out of the class, you will lose access to spells, too. Of course the other class might have wisdom-based spellcasting (as most paladin-based prestige classes have), so by all means I do not suggest that you dump wisdom, but just to add another consideration when planning your build. Even if you choose to stay as a paladin, you will not need higher than 12 wisdom for the first 8+ levels, assuming you don't care for spell DC and/or bonus spells. Finally, it is true that it boosts some of your skills (profession, sense motive and heal), but aside from sense motive you either don't have to boost them to warrant high attribute modifier or you don't really need them.
Charisma: This is important for you for various abilities: turn undead, saves, smite. Also most paladin prestige classes use charisma for various class features. Most classes have a statistic that would like to raise to extremes, due to the fact that it boosts their class features and it synergizes with most of their feat and equipment options; for the paladin class, this statistic is charisma. It will give you more turn attempts, more attack power combined with smite, higher saves and empower many of the class abilities you will pick along the way. Note that even though charisma is so good and synergistic for the paladin class, don't over-do it, especially when using the point-buy system, as that will leave you exposed. You can milk some points from wisdom, dexterity and intelligence to safely get a 16 in charisma, but going higher without the benefits that spellcasters have is probably not worth it.

Bottom line: Assuming you're in a 28 point buy game, a spread of 14/10/14/10/14/14 is gonna serve you fine. In case your stats are worse, you're better off lowering your wisdom to a minimum of 10-11 (you're not going to cast anything until level 4, so you can pump it with stat points later), your dexterity to a minimum of 8, or even your intelligence (if you choose to completely neglect skills - remember that you're always going to receive one skill point per level, no matter what). Elite array is probably best placed as: 13/8/14/10/12/15.

Races

Humans PHB: The human race offers everything a paladin needs, as a package deal, except for stat boosts. Probably the best race from the optimization scope, this offers you the bonus feat that you need, the bonus skill points without having to load on intelligence and your favored class can be any class. Additionally, the stereotypical paladin-knight is usually a human in heavy armor, so this race option gives you a lot of fluff points, too. You can also select the Silverbrow Human subrace (Dragon Magic) which loses the bonus skills, but gives you a few bonus abilities and retain the bonus feat. The biggest bonus is probably the dragonblood subtype, which increases the potential of several abilities (for instance, the feat Draconic Aura scales if you have the dragonblood subtype).
Dwarfs PHB: They get a charisma hit, but they have nice features, including keeping their natural speed in any armor and stability. A hidden bonus to the dwarf race (and most of their sub-races), is that since their speed can't be hindered, they can tumble even in heavy armor. The paladin class doesn't offer tumble as a class skill, but you can swap ride for tumble using the Cityscape web enhancement. You should seriously consider the other dwarf subraces, which do not receive a penalty to their charisma score, like Dream Dwarfs (Races of Stone) which have a penalty to dexterity instead. Another bonus that dwarfs have are the Crescent Moon Knight substitution levels, which you can access if you worship Clangeddin Silverbeard.
Elves PHB: Unless you want to grab the substitution levels, there is no reason to take them.
Gnomes PHB: While the Player's Handbook version isn't that suitable for a paladin, the gnome shadow cloak knight substitution levels are sweet. Actually, combined with Whisper Gnomes from Races of Stone, a stealth knight would be a viable choice, even though that gnome subrace receives a charisma penalty (you can use clever use of templates - for instance the Draconic template with level adjustment buyoff to offset the charisma loss).
Half Orcs PHB: As above, they get some nice substitution levels. The best subrace if you want to utilize those levels is Desert Half-Orc (Unearthed Arcana), which has stat adjustments of +2 con and -2 int, it's great to get a bonus on a physical statistic that it's going to help and a penalty to a dump statistic - otherwise you're bound to lose some charisma.
Neanderthal FB: +2 strength and constitution -2 dexterity and intelligence. Very nice race for paladins as it gets hits in the only stats you can dump and boosts those that have a big importance in battle. If you select this race you will also receive a +2 bonus on spot, listen and survival, a racial weapon focus feat with several weapons and in addition effectivelly the Cold Endurance feat.
Hellbred FCII: Very nice flavor and bonuses. They get an Evil Exception so you can use evil items without taking negative levels. They also receive several bonus devil touched feats, some of which have nice charisma related uses. Alternatively you can choose the aspect that grants bonus to charisma: it may come with a hit to your constitution, but you'll eventually get telepathy and access to the feat Mindsight (Lords of Madness), which will turn you to a huge asset to your party.
Dragonborn of Bahamut RotD: Bonus to constitution and hit to dexterity. You can give this "template" to any race, but you will lose most racial bonuses. Nice and versatile with its aspects. I would suggest the Heart or the Wings aspect.
Aasimar RoD, PGtF: Ideally this won't be necessary, but if you choose the lesser aasimar version, you can greatly reduce MAD. Also nice bonus abilities.You can also be a Dragonborn Lesser Aasimar, which pretty much offers the best attribute boni at no level adjustment: -2 dex, +2 con, +2 wis, +2 cha. You can even get the afforementioned Draconic creature template (only if level adjustment buyoff is allowed!) for +2 str -2 dex +4 con +2 wis +4 cha, at +0 level adjustment after buying it off!
Killoren RotW: Mentioned just for their flavor. They get a special smite attack several times per day.

Class Features

Paladin:

Full base attack bonus.
Good fortitude saves.
2+intelligence skill points.
d10.
Spells.

These may not seem much, but there's more to this class:

Weapon and Armor Proficiency: All simple and martial weapons, all armor and shields except tower shields. Can't get much better than this.
Aura of Good (Ex): Your aura strength is equal to your paladin level. While this has mild effects, you can stun evil creatures detecting you.
Detect Evil (Sp): Unlimited times per day, detect evil as per the spell.
Smite Evil (Su): This is the signature ability of the paladin. The power to deal extra damage with enhanced accuracy to evil beings. It is charisma based and deals damage based on your paladin level. As you gain levels, you gain more smite evil attempts.
Divine Grace (Su): Gain an unnamed bonus to all your saving throws equal to your charisma modifier. Many builds dip into paladin only for this ability.
Lay on Hands (Su): Cure some damage on yourself or your companions or damage undead. This ability depends on charisma.
Aura of Courage (Su): Give a large bonus to companions on fear effects. Also you are immune to fear. Remember that this is a supernatural effect and won't work inside an antimagic field or similar places. Immunity to fear effects is a very nice ability to have, however the aura effect isn't so good, although the bonus is morale.
Divine Health (Ex): Become immune to all diseases.
Turn Undead (Su): At 4th level you gain turn undead. This is a very important ability and its main purpose is powering divine feats. A big problem is that since you lack the ability to turn undead prior to level 4, you won't be able to take divine feats, probably until level 6 when you get the next open feat.
Spells: You prepare spells and your casting is wisdom based. You are not going to use save or die spells, so a 14 wisdom score should be fine.
Special Mount (Sp): You gain a special mount that is stronger and tougher than normal animals of its kind. For more information see the special mount entry.
Remove Disease (Sp): 1/week and an additional time per week for every three levels after 6th, you gain the ability to remove disease, as per the spell.
Code of Conduct: A paladin must be of lawful good alignment and loses all class abilities if she ever willingly commits an evil act. Additionally, a paladin’s code requires that she respect legitimate authority, act with honor (not lying, not cheating, not using poison, and so forth), help those in need (provided they do not use the help for evil or chaotic ends), and punish those who harm or threaten innocents.

There are also variant paladin classes of different alignments from Unearthed Arcana:

Paladin of Freedom:

As standard paladin except:

Class Skills: Replace diplomacy with bluff.
Aura of Resolve (Su): You are immune to compulsions and give a bonus to compulsion effects to allies close to you. Immunity to compulsions is probably better than immunity to fear, as it's probably easier to come by.
Spellcasting: You gain the spells: protection from law, magic circle against law, remove curse, dispel law, freedom of movement. You lose: death ward, discern lies, dispel chaos, magic circle against chaos, protection from chaos. Freedom of movement is a good spell to have, but so is death ward. The other spell swaps are not that important.
Code of Conduct: A paladin of freedom must be of chaotic good alignment and loses all class abilities if he ever willingly commits an evil act. Additionally, a paladin of freedom's code requires that he respect individual liberty, help those in need (provided they do not use the help for lawful or evil ends), and punish those who threaten or curtail personal liberty.

Paladin of Slaughter:

As standard paladin except:

Class Skills: Replace diplomacy with intimidate.
Aura of Evil (Ex): The power of your aura is equal to the paladin of slaughter level.
Detect Good (Sp): At will you can detect good, as per the spell.
Smite Good (Su): Identical to smite evil, only that works on good creatures.
Deadly Touch (Su): Identical to lay on hands, but it deals damage and heals undead. The main drawback is that it allows a saving throw, which isn't the case with lay on hands.
Debilitating Aura (Su): Opponents within 10ft take a -1 penalty to armor class. This is a bad alternative to aura of courage.
Rebuke Undead (Su): Rebuke or Turn, it doesn't matter what type of energy you are channeling when powering divine feats.
Cause Disease (Sp): This is bad. Not only it is subject to a saving throw, the difficulty classes for subsequent saves are all very low for high levels.
Spellcasting: Replace the standard paladin's spell list with the following spell list: 1st—bane, cause fear, corrupt weapon, create water, curse water, detect poison, detect undead, divine favor, endure elements, inflict light wounds, magic weapon, protection from good, protection from law, read magic, resistance, virtue; 2nd—bull's strength, cure light wounds, darkness, delay poison, eagle's splendor, inflict moderate wounds, owl's wisdom, resist energy, undetectable alignment; 3rd—blindness/deafness, cure moderate wounds, deeper darkness, dispel magic, greater magic weapon, heal mount, prayer, inflict serious wounds, magic circle against good/law; 4th—break enchantment, cure serious wounds, dispel good, dispel law, inflict critical wounds, poison, unholy sword.
Code of Conduct: A paladin of slaughter must be of chaotic evil alignment and loses all class abilities if she ever willingly commits a good act. Additionally, a paladin of slaughter's code requires that she disrespect all authority figures who have not proven their physical superiority to her, refuse help to those in need, and sow destruction and death at all opportunities.

Paladin of Tyranny:

As standard paladin except:

Aura of Evil (Ex): The power of your aura is equal to the paladin of slaughter level.
Detect Good (Sp): At will you can detect good, as per the spell.
Smite Good (Su): Identical to smite evil, only that works on good creatures.
Deadly Touch (Su): Identical to lay on hands, but it deals damage and heals undead. The main drawback is that it allows a saving throw, which isn't the case with lay on hands.
Aura of Despair (Su): This is good. A -2 penalty to all saving throws will come to play even at late game play.
Rebuke Undead (Su): Again you aren't going to use the main function of rebuke undead, but more for alternative uses.
Cause Disease (Sp): This is bad. Not only it is subject to a saving throw, the difficulty classes for subsequent saves are all very low for high levels.
Spellcasting: Replace the paladin's spell list with the following spell list: 1st—bane, corrupt weapon, create water, curse water, detect poison, detect undead, divine favor, doom, endure elements, inflict light wounds, magic weapon, protection from chaos, protection from good, read magic, resistance, virtue; 2nd—bull's strength, cure light wounds, darkness, delay poison, eagle's splendor, hold person, inflict moderate wounds, owl's wisdom, resist energy, undetectable alignment; 3rd—bestow curse, cure moderate wounds, deeper darkness, discern lies, dispel magic, greater magic weapon, heal mount, prayer, inflict serious wounds, magic circle against chaos/good; 4th—break enchantment, cure serious wounds, dispel chaos, dispel good, dominate person, inflict critical wounds, unholy sword.
Code of conduct: A paladin of tyranny must be of lawful evil alignment and loses all class abilities if he ever willingly commits a good act. Additionally, a paladin of tyranny's code requires that he respect authority figures as long as they have the strength to rule over the weak, act with discipline (not engaging in random slaughter, keeping firm control over those beneath his station, and so forth), help only those who help him maintain or improve his status, and punish those who challenge authority (unless, of course, such challengers prove more worthy to hold that authority).

Spell-less Paladin:

Appears in Complete Warrior.
As standard paladin except:

Spellcasting: You lose the ability to cast spells.
Blessed Weapon: Your weapon is considered good to overcome damage reduction. Mediocre as you get that from many feats and/or weapon enhancements. Gained at 6th level.
Divine Might: This is ok, but it isn't worth it dropping spells AND taking 11 levels in a paladin class without spells. Gained at 11th level.
Tend to Mount: Worthless. Just cast heal mount.
Holy Sword: Again, just memorize it.

Alternative Class Features

Charging Smite (Su) PHB II: If along a charge attack you also smite evil, you deal an extra 2 damage per paladin level (that's 3 points per paladin bonus with the normal damage boost from smite evil). The important part is that if you miss on your charge attack, your smite ability is not considered used. If you are a single classed paladin (you shouldn't) this ability boosts your damage to ridiculous amounts versus evil opponents, up to 60 - otherwise, if you prestige out at 5th or 6th level, you're just receiving 15-18 bonus points of damage. It probably works with pounce (full attack on a charge), too. Replaces Special Mount.
Divine Spirit DS: You can call a spirit that helps you and your companions. It cannot be attacked except by dispel magic, banishment and dismissal as a summoned creature using your paladin level as caster level. It stays around for rounds equal to your paladin level. Replaces Special Mount.

Spirit of Healing: This spirit can heal an amount of hit points equal to twice the amount you heal with your lay on hands ability. Moreover, it doesn't require an action on your part, as for someone to heal, he must end or begin his round on the spirit's square and use a standard action to activate it.
Spirit of Combat: +1 sacred bonus on attacks and damage per four paladin levels to all allies that are adjacent or occupy the same square as this spirit. Also weapons are treated good-aligned for overcoming damage reduction. 
Spirit of Heroism: Great tanking spirit. You gain DR 10/-, the benefit of the diehard feat and you can use your lay on hands as a free action 1/round.
Spirit of the Fallen: Fast healing 10 to all adjacent allies and 1/round revive a character between 0 and -9 hit points who is inside a 30ft range. Damage healed equal twice your paladin level.

Curse Breaker (Sp) CM: Give up remove disease and gain remove curse or remove enchantment (by giving up more uses). The good thing is that you can choose what fits better in your campaign and party , remove curse or remove disease, since you're not giving up anything else. Replaces Remove Disease.
Divine Counterspell (Sp) CM: You are giving up your main source of divine power for the ability to hurt spellcasters (and with a penalty to your effective cleric level). This is bad. Replaces Turn Undead.
Dragonscale Husk (Ex) DM: Gain a draconic armor that provides a scaling bonus as you go up in levels (but doesn't stack with any other bonus to AC), provides elemental resistances and allows for +2 max dexterity bonus (with an armor check penalty of -4). Not actually optimized, but it does have some bonuses as waving the cost of an actual armor. Replaces all your armor proficiencies.
Drakkensteed Mount (Sp) DM: Drakkensteeds have a fly speed if you consider that important. They also have trample. Unfortunately it can't command others of its kind. Drakkensteeds are also dragonblood, which can benefit you if you pick certain fits for it (for instance Draconic Aura). Replaces Standard Special Mount.
Rebuke Dragons (Su) DM: This is too campaign specific and you give up turn undead. Bad. Replaces Turn Undead.
Holy Warrior CC: Only helpful if you are actually taking a few levels of paladin. Even then, reconsider it, as lesser restoration is a first level spell for paladins and with the 4th level you can use spell trigger items such as staffs and wands, without the need to use magic device them. Feats of note are improved smiting, mounted combat, power attack (also acquired at the level you get access to divine feats, usable to grab divine might later). However note that the Holy Warrior alternate class feature is the only way to get Divine Might at level 4, or any other divine feat, since they all have the turn undead feature as a requirement.
Underdark Knight CC: If you are going to be in an underground campaign, this is worth it. You give up your mount and gain some abilities that depend on your level. Contrary to the name, this may be able to help in an underground campaign, but it applies in many situations. If you're pondering to give up your special mount for this, only consider it if you're willing to delve twelve levels deep into the paladin class, because that's where you receive the earth glide extraordinary ability - the ability to move through earth like a fish through water. While suffocation is not much of an issue, since you only begin suffocating after 2xconstitution (that's not constitution modifier - it's your constitution score), which is a really long time, you can use races that do not need to breathe - undead, warforged, air goblins (from unearthed arcana), to virtually stay in the ground for prelonged periods of time. Additionally, you receive either low-light or darkvision (if you already possess low-light vision), some minor skill boosts and an untyped land speed increase.  


Stand Fast: As an immediate action, you can add your charisma modifier to a single saving throw to all allies between 20ft or to any roll to resist a trip, grapple, bull rush, disarm or sunder attack. Replaces Special Mount
Skilled City Dweller: You can replace ride with tumble and handle animal for gather information. The first isn't too hot, but the second one is interesting.

Racial Substitution Levels

Dragonborn Paladin RotD: Add knowledge (arcana) to class skills at each substitution level.

1st level: Detect dragonblood is a lot worse than Detect Evil. You can even use detect evil to safely detect who you can smite.
4th level: You give up turn undead for some damage boost against dragons and dragonbloods. Too specific.
5th level: Gain a special mount that is immune to the frightful presence of dragons. It seems that you don't lose anything, but in fact you lose a point of BAB.

Half-Orc Paladin RoD: At each substitution level d12 hit die and intimidate replaces diplomacy.

1st level: Righteous fury is good because it works against all enemies (since it's a self-buff) and it's a morale bonus. Moreover, the activation is free, it lasts for a number of rounds based on your charisma modifier and finally: it scales with levels. Be warned that the ability RAW suggests that you will never be able to take uses of smite evil (not even from other classes).
3rd level: This is depends on your companions. If they use the stacking of fear effects, get this. Also aura of courage is easy to come by, so other characters may be able to provide it. Another way to take advantage of this ability is to use the feat Martial Study from the sourcebook Tome of Battle, and get intimidate as a class skill for all your paladin levels (not just the substitution ones).
6th level: Remove disease is probably more useful than remove fatigue, mainly because the ability cooldown is huge. I used to think that, but Remove Disease has the same cooldown, and this can potentialy negate a spell like Waves of Fatigue from every member of the party. Too bad it won't affect allies that are exhausted.

Elf Paladin RotW: At each substitution level add survival to class skills list.

1st level: Effectively makes you able to smite evil with ranged attacks. The main drawback is that you can only smite with them.
3rd level: Get a +4 morale bonus to saving throws versus enchantment effects. It doesn't mention if you receive the bonus, too, or just your allies. The 3rd level ability of paladin of freedom closely resembles this (and since most enchantments out there are usually compulsions, too, that aura is a lot better, since it makes you completely immune).
5th level: Unicorns radiate a Magic Circle against Evil, which among other things means that you and your allies within the spell's radius are completely immune to summoned creatures and mind control. That alone is already a powerful effect for 5 hours a day at so low level. However note that the unicorn will quickly lose effectiveness, since your effective paladin level for boosting its abilities receives a huge penalty.

Planar Paladin PlH: At each substitution level add Knowledge (the planes) to your class skills list.

4th level: Give up your turn undead to smite an evil outsider. Bad trade.
6th level: This is a very good substitution level, probably the best if you favor a special mount. You get the celestial template on your companion for one use of Remove Disease.
10th level: This has its uses if you travel a lot to different planes. The loss of a singe smite attempt is mild. Depends largely on the campaign.

Warforged Paladin RoE: Warforged Paladin levels grant the following class skills: Concentration, Craft, Knowledge(Nobility and Royalty), Knowledge(Religion), Profession and Ride.

1st level: Smite Construct lets you use your smite evil ability against constructs, regardless of their alignment. You don't trade anything away; the only reason not to take this substitution level is the class skills that the warforged paladin levels feature: you won't have access to Diplomacy, Handle Animal or Sense Motive, for the first few levels, but your ability to use them will be restored after your 4th level.
2nd level: Warforged characters suffer from penalties in wisdom and charisma, which are both really important for a paladin. This substitution level will help waive some of the Paladin class's MAD, by trading Divine Grace for Durable Will, an ability that will let you apply your constitution modifier on your will saves; also you're getting Repair Damage, an alternative to Lay on Hands, that's based on your constitution modifier and heals constructs and living constructs at full power, while living creatures are healed for half. This level offers you the option of completely dumping charisma in favor of a low wisdom that will let you use your spells and full-on constitution. However note that charisma often appears in many feats and features that fit the Paladin class thematically. Additionally, if you're worrying about your saves if you shun Divine Grace, check the next substitution level, which will make you immune to so many different effects, that Divine Grace will not matter that much.
3rd level: This is a perfect level - you're trading Divine Health, an ability that's almost worthless to you, since you're already immune to disease, for immunity to stunning, an immunity that's not that easy to come by with so few levels. A Warforged Paladin using these substitution levels will have a long list of things he's immune to: poison, sleep effects, paralysis, disease, nausea, fatigue, exhaustion, effects that cause the sickened condition, energy drain, fear and stunning. Effects that can still affect the warforged paladin are: mind-affecting spells and abilities, death effects, gaze attacks, polymorph and elemental attacks.

Substitution Levels from Champions of Valor

Berronar Valkyrie: Deity - Berronar Truesilver.

3rd level: Your armor, shield and primary weapon become immune to acid and rust attacks and you gain resistance to acid 5. I used to think that this was a bad trade, but it comes handy when fighting against rust monsters and similar opponents that target your equipment.
4th level: You get a conditional pounce ability, since you can activate this only if the opponent threatens a teammate and only 3+charisma times per day (which shouldn't be much of a problem). Pounce is always good and you can also combine this ability with charging smite to deal ridiculous amounts of damage versus evil enemies. Also consider the feat Battle Jump from the faerunian sourcebook Unapproachable East, as jumping on instead of charging your opponent is probably a lot easier. This remains ranked as 'black' or 'even trade', since you won't have access to divine feats without turn undead.
6th level: This is better than remove disease, because is "at will". I don't know what I was thinking, but unless you know what you're doing, spending an action at 6th+ level on a 0-level spell is usually a waste of time. The ability that makes an oath with an individual might be usable, but it's a lot of hustle for just making the target fatigued (although the effect lasts for days - one day for each paladin level at the time of the oath formation). The most useful application of this feature is that all parties involved instantly know that the oath was broken.

Claw of the Sun and Ankh: Deity - Horus-Re.

1st level: Get natural weapons some times per day. It's nice, but it's usability will diminish as you gain levels. Not only that, but the duration is limited and you need to invest a lot of levels to get it enough times per day to go through a day's encounters. Moreover, paladins lack the precision damage which is often used in conjuction with additional attacks to capitalize damage output. Additionally, the wording about smite evil suggests that you won't be able to acquire smite evil at any later levels.
6th level: Trade Remove Disease for a smite evil progression that works on members of set's church. Unfortunately it's campaign specific.
12th level: Trade one 3rd level slot for a source of light. Probably the worst trade ever. Not the worst trade, since it is a daylight spell and many monsters have some kind of sensitivity that daylight triggers (most common is Daylight Sensitivity), but there are easier ways of getting a source of light than going for twelve paladin levels.

Crescent Moon Knight: Add knowledge (local impiltur) to class skills list. Deity - Clangeddin Silverbeard/Selune.

4st level: Turn undead is strictly better than a favored enemy, especially for a nearly-worthless type like lycanthropes.
6th level: Gain the ability to cure lycantropy or even cure lycanthropes. This is perfect, since you don't trade anything.
10th level: Inspire courage for a 2nd level slot. The good news is that it's a scalable effect. The bad ones are that you can only use it once per day and that your effective bard level is four levels less than your paladin level, which means that you won't hit a morale bonus higher than +3.

Eternal Order: Deity - Kelemvor

1st level: Ignoring damage reduction of creatures is usually very good, but this ability only affects undead foes. You also gain a small bonus to knowledge (religion) checks concerning undead, but it's a mild bonus to make a difference.
3rd level: Most negative levels are bestowed by undead creatures and ignoring them is an important ability for any character. The loss of divine health is worth it.
6th level: Greater turning. This is good, because even if you have a low effective character level for turning, this is usable times/day.

Golden Cup: Deity - Ilmater

3rd level: Add any dodge AC bonus you get from Combat Expertise, fighting defensively or using the total defense to adjacent creatures. Unfortunately, RAW, you grant the dodge bonus versus your opponents, too. Unless your DM rules that only allies are affected by this, it's worthless.
4th level: Shield Other instead of turn undead. Considering that you can actually cast Shield Other (albeit at a later level) this is very bad.
10th level: Give up a smite attempt to gain a boost in your effective level for healing spells and lay on hands. The effect you gain is great for just one smite evil attempt, but at the level you're getting it lay on hands will probably be worthless (as well as your healing ability) and moreover you need to get a whole 10 character levels into paladin to get this ability.

Golden Lion: Deity - Torm

1st level: Detect magic is of equal importance to detect evil. Detect magic at will is actually an ability that's more useful in certain situations than Detect Evil; additionally, you can use it with an artificer's monocle to identify magic items some times per day.
4th level: Too specific enemies to be more important than turn undead.
6th level: This is better than remove disease. It is usable per day instead of per week. Indeed it is, but unless your dungeon master likes dead magic and wild magic zones, this is not going to come into play and obviously your Remove Disease (or any other alternative class feature you're able to swap that for) will come into play a lot more. On the other hand however, it's a really unique ability - I've never encountered a 'fix-the-weave' ability before, especially for the Paladin class.

Holy Judge: Add Knowledge(the Planes) to the skill list at each substitution level. Deity - Tyr

1st level: Favored enemy (devils) instead of smite evil. It's interesting if you acquire smite evil through other means, but don't get it unless you are going to be facing devils a lot. Note that this favored enemy gets better as you get more paladin levels, but it has no effect for other favored enemies that you might have, for example, from ranger levels.
4th level: Not a terrible ability, but this is free. Actually, it has a saving throw DC based on your paladin levels and lasts only a single round, which is bad, but at least you can attempt to Censure Devils several times per day, at a pretty good range and it's a daze effect - not many devils will be immune to it.
6th level: Zone of truth 1/week with the same progression as remove disease. Bad. The reasoning behind it is that Zone of Truth is a spell that allows a saving throw - not your best asset as a paladin. Moreover it's just a level 2 spell - you're getting those at level 8 (which is just 2 levels higher than level 6, when you're receiving the first use of this ability). It's better to have Remove Disease (or an alternative class feature that lets you swap it) that's an instantaneous effect with no saving throw and might come into play once or twice, than a spell that allows a saving throw.

Lion Legionnaire: Add Knowledge(Nature) to the skill list at each substitution level. Deity - Nobanion

3rd level: Unfortunately the aura is usable 1/day. Its duration is ok though. I don't know what I was thinking - the duration is awful as is the damage. You're better off with an immunity than this.
4th level: An extra attack for turn undead. Interesting but i would pass. Again, I must have been in a hurry back when I was ranking these abilities. All features that let you get an additional attack usually let you do so at a -2 penalty on all your attacks that round; so far so good, but what makes this awful is that it has uses per day and that you're losing access to turn undead.
5th level: Instead of animal companion get a fly speed with nice duration and cool features. You're swapping your special mount for what's essentially a 3rd level spell (Fly) with some cosmetic changes. The duration would be OK if you could break it down into several uses per day and not use it all at once, but that's not implied by the description.

Mystic Fire Knight: d8 hit die, add Knowledge(Arcana) and Spellcraft to the skill list at each substitution level. Deity - Mystra

4th level: Improved spellcasting in addition to bonus spells is one of the best alternative class features that's on par with Turn Undead. You're receiving a hefty bonus to your caster level (2+caster level from another arcane spellcasting class) and bonus spells per day that will boost your paladin caster level significantly.
5th level: This augments your smite evil without taking anything for it. Also it is a nice ability and the difficulty class is charisma based. This level doesn't take anything from your class features and adds a cool effect on your smite evil attempts, which always applies to your enemies. The duration it's just one round, but it applies to all attempts to use spells, spell completion or spell trigger items; if he fails a concentration check with a pretty good difficulty class - 10 + paladin level (note: not half your paladin levels) + charisma modifier + spell level (so even for a level 1 spell you're looking at DC 17-18+); in addition it probably applies to enemies that are not evil, although you'll have to check with your dungeon master on that.
6th level: Targeted greater dispel magic using your paladin level as caster level times per day for weakly uses of remove disease? One of the best substitution levels. You're getting Greater Dispel Magic, which is an awesome spell that can be applied nearly to all combat situations; plus you can use it once per day than once per week; plus it doesn't require an action and you just make the decision before you roll for an attack; plus the caster level cap is at +20 and you get to add any arcane caster level you may have from another class to it. This is one of the best substitution levels and it just takes away from you Remove Disease, one of the borderline features of the class.

Noble Heart: Add Survival to the skill list at each substitution level. Deity - Ilmater

3rd level: For the price of your Divine Health class feature, you get Track as a bonus feat and a hefty bonus to your survival skill for tracking followers of Loviatar. Since the Track feat requires you to hit respectable survival checks and you only receive it as a class skill for the substitution levels, don't expect to be extremely good at it. This is a perfect alternative class level for fulfilling requirements for a certain prestige class or feat you need.
4th level: Give up turn undead to sunder followers of Loviatar. It's just too specific to be useful.
6th level: Gain weekly uses of delay poison instead of remove disease. Ok trade. Again, as with Zone of Truth, Delay Poison is just a second level paladin spell and with just two more levels you can cast both Remove Disease and Delay Poison if need be. Only take this if you absolutely know that you'll be facing lots of poison-using enemies, e.g. if you're campaigning against the Drow or the followers of Loviatar.

Red Falcon: Add Knowledge(History) to the skill list at each substitution level. Deity - Red Knight

2nd level: Trade divine grace for a below average ability. Bad. Actually the ability is not that bad and since the AC bonus is insight, it works on your touch AC, too; essentially a 'no' to enemy spellcasters that target you with rays and spells that require ranged attack rolls. However, the ability can be used limited times per day (albeit at immediate action speed) and it replaces Divine Grace which is one of the best Paladin class features.
4th level: Swap three of your turn attempts for an extended spell list - Augury, Deathwatch and Status. The trade is ok if you really want some or all of those spells, it's better to lose three turn attempts than your whole turning ability altogether; however note that none of these spells are groundbreaking and deathwatch has the [Evil] descriptor, which is just weird.
6th level: This is a very good substitution level, since you're just trading a 1st level spell slot for a free Extend Spell on one of your paladin buffs, regardless of level - and you don't even have to possess the feat. In addition, virtually for free, all your cohorts and followers can be trained in the use of a martial weapon as long they remain in your service and you regularly train them; they don't all have to be trained in the use of the same weapon, so you can grant different proficiencies to different cohorts and followers.

Ruby Rose Knight: d8 hit die, add Bluff and Perform(dance, oratory, sing, string instruments) to the skill list at each substitution level. Deity - Sune.

3rd level: Divine health has more uses. I don't know what I was thinking, but making you immune to effects that deal damage or drain to your charisma, probably a statistic you'll want to be high, is very good. Protects against certain character optimization staple spells or powers, such as Ego Whip and the feat Twist the Knife.
6th level: Heroism per week instead of Remove Disease. Normally it would be superior, but i think that on weekly basis, remove disease is better. Actually the trade is more or less equal; either you select an effect that removes negative conditions from your teammate (or you, assuming you traded Divine Health for Enduring Personality) or you get a combat buff that grants morale bonuses, so it will be useful for many levels. A note is that if your party features a Bard, you're better off with Remove Disease as most of their buffs are morale effects, too.
12th level: Nice buff, but not worth it the 3rd level slot. In any way, don't advance to 12 level just for this.

Vigilant Eye of Helm: Deity - Helm

1st level: This is an ok trade and see invisibility is free. You can't actually detect invisible enemies, since this ability depends on your normal senses, but you it is activated automatically and doesn't require an action from your part - unlike Detect Evil. It's very good when you're leading your teammates against groups of enemies and not facing a single foe, because you can direct your strongest debuffs and abilities towards the strongest of your opponents; this ability updates automatically if certain foes leave the battlefield or die! In addition you get to add See Invisibility to your paladin spell list.
3rd level: Not worth it for divine health. Actually, this ability is not that bad at all, especially if you're using the Complete Adventurer rules for the Aid another action, which rules that you can give scalling bonuses to your teammates when using that function, according to your base attack bonus or if you're sporting an Amulet of Teamwork from Magic Item Compendium. You also get to use this special aid another action as a move action, so you get to attack or use your standard action as you see fit.
4th level: You do trade turn undead, but awesome blow is a very nice feat. Indeed it's not that bad of a feat, but you must know what you're doing; the Awesome Smite entry doesn't mention whether you have to get a -4 penalty on your attack roll to activate it or it is activated just by virtue of spending your smite evil attempt. Even then, you must optimize your attack damage, because that's the saving throw difficulty class against your awesome smite. Finally, because you're only going to have the chance to use this ability once or twice per day, until really late levels, it's best if you stick with turn undead and pass on this feature.

Wary Swordknight: Add Listen and Spot to the skill list at each substitution level, 4+int skill points at each substitution level. Deity - Arvoreen

3rd level: This is a nice trade for halfling frontliners. You won't regret it. I find being protected against fear tactics (immunity to fear effects) and in addition providing a big bonus to your teammates against the same effects is more important than getting bonuses against opposed checks; this only works if you want to be able to utilize trip effectively, so only get it if you're planning on following that route.
4th level: This on the other hand isn't worth it. You can gain uncanny dodge with a lowly feat.
6th level: The Haste spell is one of the best 3rd level spells in the game and it does not appear on the Paladin spell list. It is definitely worth the trade of the standard Remove Disease spell-like ability, since you are able to use it every day instead of weekly.


Harmonious Knight: Add Perform to the skill list at each substutition level. Deity - Milil

1st level: Mediocre. The problem is that they don't get better as you gain levels. They might, but inspire courage is better than detect evil and these substitution levels offer you perform as a class skill, which means that you can take the feat From Smite to Song from the first level (inspire courage for a smite attempt, look at the feats section).
6rd level: As above. Remove disease is not that useful, but inspire competence is not going to be useful, either. Only get this if you want to qualify for a feat or prestige class.
9th level: On the other hand, inspire greatness is a lot better than an extra use of remove disease. What really shines for this ability is the 2 bonus hit dice people affected receive. That is an average of 11 bonus hit points and the difference between life and death in certain situations (like spells that only check your hit dice , like dictum, holy word, etc). You can also get Words of Creation, a feat from Book of Exalted Deeds, which will double your inspire courage ability and also give you four bonus hit dice from inspire greatness.

Shadow Cloak Knight: Add hide and move silently to the skill list at each substutition level. Gnome.

4th level: You get Favored Enemy(Humanoid) without a trade and you're free to choose to which subtype your favored enemy class feature will apply. Unlike Holy Judge's Favored Enemy(Devils), this ability actually seems that it advances any other favored enemies you might have (from Ranger levels for instance).
6th level: You get Hide in Plain Sight and you don't trade anything. This level coupled with respectable ranks in the hide skill will make you able to act as a stealth knight! Remember that you can use Whisper Gnomes which receive better land speed and improved hide and move silently bonuses.
9th level: Again without trading anything, get 1/day Invisibility.

Charisma Synergies

The X stat to Y bonus thread is a very useful tool for determining what type of synergies you can acquire, as well as their investment (just by looking the type of the entry - for example a feat is probably easier to qualify for than a prestige class - or with some book search). The tables can be sorted by column (just click on the column name), which is handy for different searches; for instance you might be looking of ways to get charisma as a bonus to your attack roll - then just click on the "bonus" column; or you might be looking for specific books as sources - click on the "book" column; or you might just want a feat or item, because your build is already planned and well-thought out - click on the "type" column.

Using that table I've generated the following results for easy reference (note that I've stripped all the entries that are not 3.5 (e.g. 3.0, PF) or they're from a dragon magazine).

Races

Killoren (Destroyer Aspect) RotW: To-Hit (limitations).

Prestige Classes

Risen Martyr 2 BoED: Saves.

Champion of Gwynharwyf 2 BoED: Saves. 
Slayer of Domiel 2 BoED: Saves.
Dread Pirate 9 CV: AC, limited uses.
Exemplar 4 CV: Fort saves, concentration.
Holy Liberator 4 CD: Saves.

Tattooed Monk 5 CW: Any attribute, limited uses.
Blackguard 2 DMG: Smite, Saves.
Platinum Knight 5 DrN: Saves (vs evil dragons).
Eldeen Ranger 3 ECS: Saves (vs greensingers).
Corrupt Avenger 3 HoH: Saves (doesn't stack with divine grace).
Tomb Warden 3 LM: To-Hit, Damage, Saves (limited duration).
Defiant 2 PlH: Saves (vs divine spells).
Justicar of Tyr 5 PGtF: Saves (vs chaotic outsiders). 
Martyred Champion 4 PGtF: Saves. 
Chameleon 3 RoD: To-Hit (limitations).
Walker in the Waste 10 SS: Hit Points.
Knight of the Sacred Seal 2 ToM: AC, Reflex saves (limitations).
Master of Yuirwood 9 UE: Saves.

Classes

Red Falcon 2 CoV: AC, limited uses. 
Samurai 3 CW: Damage, limited uses.
Hexblade 2 CW: Saves vs Spells.
Wilder 2 XPH: Touch AC (cannot exceed normal AC).
Azurin Cleric 1 MoI: Essentia (limitations).
Soulborn 1 MoI: To-Hit (limitations).
Marshal 1 MiH: Varies, affects allies.

Feats

Ascetic Mage CV: AC.
Force of Personality CV: Will saves (replaces wisdom).
Divine Shield CW: AC, limited uses.
Divine Might CW: Damage, limited uses.
Evil Blessing EE: Saves (profane, limited duration, unlimited uses).
Snowflake Wardance FrB: To-Hit (limitations).
Smite Fiery Foe FrB: To-Hit (limitations).
Unnatural Will HoH: Will saves (vs fear).
Combat Panache PHB II: AC (limitations).
Spiritual Force RoE: Damage (limitations).
Avenging Strike ToB: To-Hit, Damage (limitations).

Domains

Mysticism SC: Saves (limitations).
Halfling PGtF: Climb, Jump, Hide, Move Silently (limitations).

Items

Slippers of Battledancing DMG II: Damage, To-Hit (limitations).
Bow of Song MIC: Damage, To-Hit (limitations).
Hexband MIC: Damage (limitations).

Feats

General:

Leadership PHB: This is one of the best feats you can acquire both for flavor and optimization reasons. Most DMs ban this outright. Paladins have a special mount and unless they swap that class feature for an alternative one, they are already looking at -2 points, however, since your leadership score is the sum of your level and your charisma modifier and you're able to receive most positive modifiers to your score just by doing your job right (great renown - fairness and generosity), raising your score high enough to effectivelly get another player character under your control will be extremely easy. Don't forget about followers, too - they can also be used, even though their combat effectiveness will be limited (you'll require resources to keep them around with you and they're too weak to survive direct confortation), unless the situation is a siege of your personal keep, where they will mostly be using ranged weapons. To optimize the Leadership feat even more, you can check out Heroes of Battle, which features some feats that can boost several aspects of the leadership feat (Extra Followers, Improved Cohort, Practiced Cohort, Inspirational Leadership). More sources: Legendary Commander ELH, Epic Leadership ELH, Dragon Cohort DrN, Undead Leadership LM, Might Makes Right RoF.
Practiced Spellcaster CD: As a paladin you'll have very bad caster level - just half your paladin level; the problem is that if you favor buffs that benefit from caster level (like for duration, effects and so on), practiced spellcaster can be used to pump it up a bit. Remember that if you're planning to use it, it has a spellcraft skill requirement of 4 ranks, which is a cross-class skill for the paladin class.
Goad[Retrain] CV: Great for charismatic front liners. You can attract an enemy and survive since paladins are usually nice tanks, but also save a weak opponent. This feat is not that great, because it has multiple restrictions and only prohibits melee attacks on your teammates. However, it's a great feat for your starting levels and you can opt to retrain it later; this is because it will start to lose effectiveness as you'll start encountering enemies with different movement modes than land speed - for instance any flying creature is difficult to goad, unless you also possess a flying speed or the creature has a large threat range. The controversial thing with this feat is that it is based more on your opponent, than on you (except from the DC of course), because it relies on his or her threat range. This feat is very good against opponents with weak will saves that either have large reach or require mobility to be effective (e.g. chargers); in addition, assuming that your opponent is only dangerous with his melee attacks, you can use this to save a weaker ally, by forcing the enemy attack you.
Winter's Champion FrB: You add the spells from cold and winter domains to your class spell list. The spells are unimpressive and mostly deal direct damage.
Draconic Aura DrM: Project a draconic aura. This is very useful and flavors with the auras/buffing effects the paladin already has. Indeed, this is very good feat and fits the class thematically, assuming you've got the [dragonblood] subtype. The best thing is that this feat provides a great deal of versatility: you've got a wide selection of auras to choose from and most will benefit all the members of a party. Obviously you should check with your teammates and choose an aura that boosts the party's most important abilities. The Energy aura is very good to help a primary spellcaster that employs spells of a particular energy type - e.g. a spellcaster that specializes in cold using the Snowcasting feat - that way you can provide him with a pretty good bonus to his difficulty class. Note that the same applies to any ability that has the appropriate descriptor or deals damage of the chosen type, so, for example, it might help a Dragonfire Adept, too; the Insight aura will be mostly useless - the only use I can think of that will benefit a party is if most of your allies grab the Knowledge Devotion feat; if your party features more than one offensive spellcasters, then they will probably love the free Spell Penetration feat(s) provided by the Power aura; Presense boosts the social skills Bluff, Diplomacy and Intimidate - while these skills are all worthwhile, unless your party uses the demoralize combat action, it's not worth it to boost them via an aura; the Resistance aura is good for the first levels - a party that will crusade against pyromaniacs will gladly get the extra protection, but after some levels the energy protection will quickly lose effectiveness; Resolve helps against fear, paralysis, sleep effects and concentration checks, but it doesn't boost any other saving throws - you're already immune to fear, you give a +4 morale bonus to your teammates and getting a +4 max bonus on saves versus paralysis and sleep effects, while useful, isn't good enough; Senses is probably the best non-specialist (that is, if you exclude situations that another aura is more useful, because of your party composition) aura you can pretty much acquire - at the end you're essentially giving everyone a little more than three bonus feats (Improved Initiative, Skill Focus[Spot], Skill Focus[Listen]). Having good spot and listen checks is fine, but the important thing here is the initiative bonus; i don't really like the Stamina aura, but the bonus to fortitude saves is well worth it; Swiftness is another great choice for parties that value mobility (or lack in that sense) - the skill boni are good, but getting +10ft movement speed to all movement modes at an early level (7th) to all of your party members for just one feat is heavenly; and finally, the Toughness aura is obviously not worth it, since it can be easily bypassed by magic weapons.
Daunting Presence[Retrain] LM: A charisma based will save feat that can make opponents shaken. Since most paladins will not have the Intimidate skill as a class skill, if your party employs demoralize/fear tactics and you want to participate, then this feat will make it happen. Note that this has to be used as an opening or finishing move versus an opponent - it makes people shaken, but it has no effect if a creature is already shaken; it arguably works versus targets that are frightened (since shaken + shaken = frightened, your target is no longer shaken), so, for instance, you can open with daunting presence, have someone make your target shaken again and then use your daunting presence once again to make him panicked. Daunting presense has a charisma-based difficulty class and scales as you level up, because it's based on your hit dice; moreover it's a ranged ability - you don't have to be threatening the enemy with your weapons, just to have a staredown contest! As you gain levels, if your enemies are frequently immune to fear or mind-affecting effects, or you just have better things to spend your standard action on, you can just retrain it.
Avenging Strike ToB: Unless if you are going to deal with creatures who possess the evil subtype, take this. Otherwise it's not worth it. Note that this works if the outsider has the evil subtype, regardless of alignment (it means that you can avenging strike paladin outsiders for example that have the evil subtype). Avenging strike is a very elegant feat that would probably be a very popular choice among those builds that favor charisma synergies, but, unfortunately, it can only be used on specific creatures - those outsiders with the [Evil] subtype. Since it requires you to have a good alignment, that probably means that you're thinking of a build featuring the traditional paladin class, so you will almost definitely encounter evil outsiders at some point in the campaign, but whether they will be enough to justify you picking this feat is debatable. Check with your DM - if you're going to delve into the Abyss or Nine Hells, then it's a quite good pick; otherwise it's better to pass on it. Another little detail: it probably is a typo, but, as written, if you use a swift action to empower your attacks, that energy lasts until your next attack - it doesn't have a duration (like 1 round), so you can probably prebuff your weapon with it (although it will be discharged on your next attack, whether you hit an outsider with the [Evil] subtype or not) so that you can use your swift action on something else.
Dilate Aura FCII: Double your aura's range once per encounter for rounds equal to your charisma modifier. Mediocre. Indeed, it's not an ability to die for, but I wanted to note that a paladin with many followers from the Leadership feat will probably make the best use of this feat. Too bad that as written you can only enlarge only one of your auras.
Sword of the Arcane Order CoV: This is a gem. One of the best feats for paladins out there. To elaborate on this beautiful feat: it enables you to memorize sorcerer/wizard spells in your paladin slots, using your own spellbook or a borrowed one; in addition your wizard caster level is treated as the sum of your wizard, paladin and ranger levels. So, to list the disadvantages, since the advantages are pretty obvious: you can't dump Intelligence, as you'll need it in order to cast wizard spells through this feat; since you're not going to have a really high intelligence modifier or the ability to use high level spells, you're restricted almost exclusively to buffs; you're restricted to specific deities (Azuth or Mystra), even though that's not really a problem, since Mystra's order, Knights of the Mystic Fire, features some sweet substitution levels; it is unclear whether you can have a spellbook without levels in the wizard (or wu jen) class - if you can only get your own spellbook by dipping those classes, you can either choose to dip or invest in spellcraft and use borrowed spellbooks - be warned that the spellcraft DCs to memorize spells from borrowed spellbooks are quite high, at 15+spell level; the way that the caster level calculation for wizards is worded, seems to debuff caster level and to always set it at wizard + ranger + paladin levels, making feats like Practiced Spellcaster worthless - it wouldn't be that way if the ability was just "you add your paladin and ranger levels to your wizard caster level" - I don't think this is RAI, though, and it will rarely matter, since you'll need to dip 4 levels in the Paladin class anyway. An issue you'd most probably like to clear with your DM is whether the spells you cast using this feat are arcane or divine. In the case they are arcane, you'd have the additional restriction that they are subject to arcane spell failure, but you'll be able to qualify for prestige classes, feats, abilities or items that require you to be able to cast arcane spells and activate eternal wands. In the case they are divine, they are not subject to arcane spell failure, but you'll be able to use them in conjunction with abilities that only work on divine spells (for instance the Divine Metamagic feat, check Complete Divine's errata) and create scrolls of arcane spells that are treated as divine spells (your Archivist party member will love you).
From Smite to Song CoV: Spend a smite attempt to activate a inspire courage effect with effective bard level equal to your paladin level. Average feat. I used to think that, but actually this feat has a number of uses. First of all inspire courage is one of the best bard songs and the most common target of optimization (boosting its bonuses via feats and items); you only spend a feat to get the best class feature of a class and it automatically scales, too! The downside is that it scales according to your paladin level, which is not that good, because you'll normally want to prestige out as quickly as possible. In addition, it requires you to worsip Milil, a deity that offers some interesting substitution levels; if you get the first level of Harmonious Knight, you'll be able to get this feat from your first level (as it requires 3 ranks of perform and the substitution level makes perform a class skill for you).
Battle Blessing CC: A gem. Auto quicken nearly everything on your spell list. A must if you are going to value spellcasting. In truth Battle Blessing does not affect nearly everything on your spell list, but over 100 paladin spells benefit from it. Since this feat only works with paladin spells, you'll most probably have to stay in the class, or choose prestige classes that advance spellcasting; this is actually a negative, but you can work something out by selecting alternative class features and abilities that depend on your paladin level (for instance the From Smite to Song feat, or the Charging Smite alternative class feature). What Battle Blessing does for your combat buffs is invaluable - it can be used on helpful combat spells such as Divine Favor, Bull's Strength, Holy Sword, Magic Circle against Evil, Protection from Evil, Shield Other and you are free to full attack or even employ another buff (assuming it originaly had a casting time of 1 round, since you only have one swift action per round, normally).
Dreadful Wrath PGtF: This is a very good feat for every charismatic character. Create a fear aura every time you attack, charge or target an enemy with a spell.

Combat:

Spirited Charge Line PHB: If you're looking to play the paladin class in a core-only (or close to core) environment, utilizing a mount and a lance, the iconic 'knight' image, this is a valid way to work towards a respectable damage output. All you'll need is a good source of damage that will be multiplied - your best bet is the Power Attack feat. Of course, you'll
Power Attack PHB: Trade attack bonus for extra damage. Nice feat.
Martial Study/Stance ToB: There are some great maneuvers you can benefit from. Also you get new class skills, the most important of which, i consider to be intimidate from devoted spirit.
Stone Power ToB: If you happen to possess stone dragon maneuvers, this boosts your defensive capabilities even more.

Smiting:

Extra Smiting[Retrain] CW: This is not necessary, but it's there if you are continually using smite attempts. As written, you probably get two additional smite attempts that you can use for various smite class features. It's obviously a good feat for your starting levels and if you get enough smite attempts to use per day, you can retrain it for something better. Unfortunately it requires four points of BAB, so you won't be able to pick it up as a starting feat - where it's probably most needed.
Improved Smiting CD: This is nice if you have a problem with overcoming damage reduction. Also useful if you have also other kinds of smite. Indeed, this is an option if you have problems with damage reduction, but the paladin class is feat-starved, so it's better that you let your equipment take care of it; fortunately you're getting a mild damage boost to your smite attacks, but unless you've got a lot of them, don't bother with this feat; it's only worth taking if you've got a large amount of smite attempts per day and if they are 'special', meaning that they're not aligned, but affect something else, for instance, the smite the Killoren race gets.
Exalted Smite BoED: This is worthless. Just take improved smiting, which gives you a bonus to your damage, too.
Smite Fiery Foe FB: Use this if you are going to encounter fire based creatures, such as fire dragons. This feat is so bad, that even against fire based creatures - that is creatures that have the [Fire] subtype - can be worthless, as it adds just elemental damage, easily negated by spells and abilities. On the plus side, you do get a bonus smite attempt and you can convert other smites (but only from character levels or cleric domains, so Killorens are out) to "smite fiery foe"s, but unless you're convinced that you're going to be constantly battling creatures with the [Fire] subtype at relatively early levels, better stay away from this one.
Ranged Smite Evil BoED: You can use a smite evil attempt through a ranged weapon. Great if you want to play a ranged paladin. The other alternative, is using the elf paladin substitution levels, but obviously that option has two main drawbacks: you've got to be an elf and the weapon selection to deliver smite evil attacks is restricted to longbows and shortbows (with their composite versions), however, it doesn't eat up a feat. Both versions share the same drawback: you can only smite evil with them and you can't use other smite types.
Smiting Power CoV: Smiting power is not very powerful, but it can be used as a connection between your innate paladin powers and special combat maneuvers, should you decide to use them. Between the overrun and the bull rush maneuver, the latter is easier to optimize without sacrificing too much of the resources available to you; selecting some feats (Knockback RoS, Jotunbrud RoF, etc) or items (Brutal Surge enhancement MIC) or even the Dungeoncrusher Fighter variant (just a 2 level dip is required), will greatly increase your bull rushing capabilities and Smiting power will add charisma synergy to the mix.
Awesome Smite CC: Ignore some damage reduction points, trip opponents or ignore miss chances against opponents you smite. Great maneuvers. This feat enables you to use three maneuvers; each of which requires that you make a smite attack while using the Power Attack feat (minimum attack penalty -1). As written, this feat enables you to use the maneuvers, whether your target is valid for your smite type or not. Demolishing Smite will easily cut through any damage reduction - it ignores damage reduction points up to twice your charisma modifier, which, will easily be 6+; Overwhelming Smite is a weird one - if you hit and deal damage with your attack you can treat your attack as though it was a trip maneuver; if you get your hands on Improved Trip somehow, you immediately gain another attack against your opponent! So it's like using a smite attempt to gain a free attack (other certain conditions of course, but it can work) - however note that tripping is not always effective (e.g. against flyers); finally, Seeking Smite will enable your attack to negate any miss chance your opponent might have, which is very useful against many buffs (Displacement for instance).

Divine:

Divine Cleansing CW: The bonus is limited to +2 and it's only for fortitude saving throws. Unless your party is consistently making fortitude saves against hazards, better stay away.
Divine Might CW: Add your charisma to damage for 1 full round. This provides even more charisma synergy. Great feat. Just to note that Divine Might increases your charisma synergy, but you will be able to use it less than 10 times per day, unless your charisma modifier is really high and you don't have to spend turn attempts to power other divine feats. Obviously, since divine might affects appies to the attacks that you make in a full round, to get the most out of this feat you need to get more attacks per round; however, the Two Weapon Fighting feat line is out, as it requires a lot of dexterity investment on your part, which, as a Paladin, is not a good option. A great solution to get more attacks per round is to acquire secondary natural weapons, such as claws, tail, bite, etc - you will attack with a big penalty (-5 modifier to attacks), but that applies only to your secondary natural weapons - not your original attack sequence. Another note is that if you want to play a Paladin that utilizes ranged weapons (maybe using the elven substitution levels), Divine Might applies to all weapon damage, not just melee ones! Of course, to qualify for it you need to have Power Attack.
Divine Resistance CW: All allies in a 60ft burst gain resistance 5 to cold, fire and electricity. Unfortunately requires divine cleansing and isn't that powerful, so you better skip it.
Divine Shield CW: Close relative to divine might, this feat makes you a walking fortress and has a pretty nice duration. This is another feat that will enhance your charisma synergy. Unlike Divine Might, Divine Shield has a scaling duration, which increases according to your character level; this enables you to save some turn attempts to fuel other divine feats, as you won't have to activate it each round. The bad news is that you'll have to spend the first round of combat to power up your shield, as activating Divine Shield takes a standard action. If you somehow manage to squeeze two fighter feats in your build (possibly dipping into fighter or psychic warrior) you can grab Shield Specialization PHB II and Shield Ward PHB II; the first is rather uninteresting and dull - it just increases your shield AC by one point with the selected shield group (light, heavy or buckler), but it grants you access to the second feat, which will let you add your shield bonus to AC (remember that figure is enhanced by Diving Shield) to your touch AC and checks or rolls to resist attack options like bull rush, disarm, grapple, trip or overrun.
Divine Vigor CW: If you are wearing heavy armor, your speed will be greatly reduced. This not only pumps your speed, but also provides you with 2 temporary hit points/level. The effect has a duration of minutes/level. Great feat. Actually the feat is good, but the activation is not; if you're going to spend a round buffing, you are not going to do it for some temporary hit points and bonuses to speed; this is only useful if you know that you are going to face an enemy within minutes, which makes it a luxury feat.
Sacred Vengeance CW: If you want to hurt undead more, you can purchase an undead bane weapon for the same effect 24/7. Fortunately, this affects all your melee attacks until end of turn, just like Divine Power.
Divine Metamagic CD: Probably not useful to you as to clerics, you are better off with metamagic rods. I don't know what I was thinking about this - it's obviously very good, but you'll have to commit some resources to make it work. For example, getting the crowd favourite DMM(Persistent Spell) you'll have to reserve three feat slots and the amount of turn undead attempts you will have to sink into this feat will make you unable to take any other divine feats. The main problem is that paladins do not have many spells that are worth it to be made persistent; the most common choices are Bless, Divine Favor, Blessed Aim, Divine Sacrifice, Strength of Stone, Find the Gap, Prayer, Sacred Haven, Blessing of the Righteous. If you are allowed to persist wizard spells by using the Sword of Arcane Order feat, then a whole lot of options open up for you - for instance using the Thunderlance spell which creates a lance of force with great reach made out of pure force, which will let you attack and deal damage using your charisma instead of your strength modifier. If the sourcebook Complete Champion is not available, you can use DMM(Quicken Spell) to quick cast some buffs in-combat, because that will bar access to the Battle Blessing feat. Finally, you can probably make use of DMM(Empower Spell) because there are some combat buffs with variable effects.
Divine Spell Power CD: This requires a special turning roll with a +3 bonus to the roll. If you optimize the roll a bit you can easily get 1-2 bonus to your caster level. Mediocre.
Glorious Weapons CD: Align melee weapons of your allies in a large area to good/evil. Average feat. It's like casting a limited version of Align Weapon, Mass, which is actually a 3rd level feat. It's not that bad, especially if you regularly find yourself in battle with creatures that have a damage reduction type that  can be bypassed by this feat; for instance some devils or demons. 
Sacred Boost CD: This maximizes the next healing spell cast on the subjects affected. Average; you are not going to memorize traditional healing spells. 
Sacred Healing CD: This is a very good ability. You effectively provide your allies healing 3*(1 + your charisma modifier). Be careful as this feat affects all living creatures, which includes enemy living creatures. Exactly because it can potentially affect enemies, you need to spend a full-round action to activate it  (!) and it requires 8 ranks in heal, which is not the most essential of skills and the effect is nothing to die for, just more healing, this feat can only situationaly justify its appearance on a paladin build. However note that Sacred Healing doesn't scale according to your levels, only according to your charisma modifier - unfortunately, because of the skill requirement you can't get it at early levels and retrain it later, which would be obviously a lot more useful. 
Dragonfire Channeling DM: Not good since your effective cleric level is low.
Divine Accuracy LM: You and allies can reroll the miss chance with melee attacks for incorporeal undead. It is too specific to be good, and in any major incorporeal undead campaign you are better off with ghost touch weapons or truedeath crystals.
Profane Lifeleech LM: Spend two turn attempts to deal 1d6 points of damage to all living creatures in a 30ft burst and heal the total amount of damage you dealt. This isn't an offensive feat but more of a healing one. Also it might work if you have tomb-tainted soul as it doesn't state that the healing energy is positive.
Profane Vigor LM: Heal an undead ally 2 hit points per cleric level. Even assuming that you can use your paladin level instead of a cleric level, this feat is bad. Just use your deadly touch ability.
Sacred Vitality LM: Use a turn attempt to gain immunity to ability damage, ability drain and energy drain? And for 1 minute duration? This is probably a must have. Indeed the feat is great, but it requires a little bit more explanation. First of all, its duration is just one minute and it requires a standard action to activate it, but it grants you protection against ability damage, ability drain and energy drain; needless to say, all these types of attack can be potential threats to your combat prowess; ability damage and drain that target your physical attributes or charisma can limit your power and energy drain directly lowers your saves, skill checks, attack bonuses, hit points and your best (i.e. highest level) spells. In addition, it is useful not only against undead creatures, as it is common with [Divine] feats, but against a wide variety of enemies and attacks (e.g. the psionic power Ego Whip).
Spurn Death's Touch LM: Heal ability damage, remove paralysis effects or negative levels by spending turn attempts. Nice if you are going to be fighting undead, otherwise skip it. It doesn't have the versatility of sacred vitality.
Blackwater Invocation SW: Deal some non important damage with a pesky difficulty class, while giving concealment to the creatures in the area you affect. Worthless.
Sanctify Water SW: Unless you have a plan to trap undead in bodies of water and using this afterwards, don't take it.
Divine Spirit ToB: If you are in a devoted spirit stance, you can expend a turn attempt to heal yourself for 3+ charisma modifier damage. Average. Bad.
Divine Armor PHB II: Give your armor damage reduction 5/- for 1 round. I don't think it's worth it, unless you couple it with feats that force enemies into attacking you, for instance, the goad feat. Note that this feat requires a divine caster level or 5 (this means, paladin level 10).
Divine Fortune PHB II: On the other hand, this can help in early levels when your saves and charisma won't be too big. It's an immediate action. Later you can retrain it. Unfortunately this is worthless, as it requires a divine caster level of 5, which you won't possess at early levels - skip it. 
Divine Justice[Retrain] PHB II: This is interesting if you are a purely defensive character without large damage outputs. Targeting rogues or melee skirmishers can give you large amounts of damage easily. Also there are effects that diminish damage after it is dealt (fortification armor negates critical hits, damage reduction, fast healing, general healing). This is a perfect feat for your early levels if for whatever reason your damage output lacks (for instance, you might be a member of a small-sized race, a halfling or a gnome, so early levels will be kinda difficult to get by) and you consistently deal with single 'bosh'-type enemies; you can retrain it later for something more useful. 
Divine Ward PHB II: This is more important to clerics than you.
Profane Aura PHB II: Nice ability to battlefield control a bit, but a two-bladed knife. Divine caster level of 9th means that, even if you get Practiced Spellcaster, you'll already need to have 14 levels. 
Sacred Healing PHB II: This again, is best used by clerics. Actually, it is bad, even for clerics; to make the best out of it you need healing spells that allow you to roll a high number of dice and paladins do not have spells like that. 
Sacred Purification PHB II: This requires sacred healing. There is a sacred healing feat in complete divine by the same name. It is strictly better (in regards to long term healing) to both this and the previous feat.
Sacred Radiance PHB II: Nice feat with bonuses to allies and penalties to foes, but you must have caster level 9 to grab it. Actually, this is a lot like Divine Cleansing, if you count that all those saving throw bonuses are fortitude based, except fear. It also debuffs your enemies' saves against fear effects, but for the level you are going to get it, expending a standard action for a minor penalty (-2) is just bad. Only consider it if you are in a party that uses stacking fear effects and even then, only as a luxury (or thematically 'correct') feat. 
Divine Censure FCII: Spend a turn attempt to shaken all evil outsiders within 30ft. The ability lasts for charisma modifier rounds and has a charisma based difficulty class; even though this feat has charisma synergy, it's too specific to be of use. 
Divine Defiance FCII: This isn't useful to you. It screams cleric. To be more specific, you just won't have enough spells prepared for this feat to be useful, while a spellcaster with access to turn undead (typically clerics) will have a greater variety of spells prepared and, thus, a larger chance to counter a spell. 
Divine Justice FCII: This is actually nice. "Evil outsiders" covers a lot of creatures and you get to shaken them, too. Actually "evil outsiders" covers a lot of creatures, but unless you're going to campaign against devils or demons or yogoloths, this feat will not very useful. Besides, if you count the shaken effect out, the damage is not that great - 2d6 averages at 7 points of damage, which you can get with Divine Power if you have a high enough charisma modifier. 
Persistent Refusal FCII: Your saves are already very high. Taking this can guarantee that you won't be disabled for a lot rounds. It's like a better version of Slippery Mind, but it requires the expenditure of a turn attempt in order to work. 
Pious Defiance FCII: I prefer divine fortune that covers all your saving throws. Divine Fortune requires a high caster level, thus, you won't be able to pick it up at early levels; still this fact does not make this feat any better - it scales with levels, but it only help your will saving throw. 
Retrieve Spell CC: This is nice especially with things like sword of the arcane order and the like. Unfortunately no. Retreive Spell requires you to already possess two divine feats in order to acquire it, so you can use it to regain some combat spells, but it takes a big toll 
Spiritual Counter CC: Too many turn attempts needed.

Class Stacking:

Ascetic Knight CV: Monk and paladin levels stack for unarmed strike and smite evil damage. Obviously, the main purpose of this feat is to dip into the monk class for 1-2 levels and then use Ascetic Knight to benefit from the increased damage, possibly by getting feats, items and abilities that further increase your base unarmed strike damage. If you're looking to make the best out of the monk dip, take a look at the Overwhelming Attack variant monk from Unearthed Arcana, which can set up a charging base for Shock Trooper and similar feats, the Feign Death or Invisible Fist or Spell Reflection alternative class features if you're looking for ways to get rid of your Evasion ability, the Decisive Strike variant that replaces Flurry of Blows with something that's more useful (you can also combine it with Scorpion Kama from Magic Item Compendium). If you're playing in Eberron, you can also trade your 2nd level bonus feat for the Whirling Steel Strike feat, which lets you treat the longsword as a special monk weapon. 
Devoted Inquisitor CV: Smite evil and sneak attack to potentially daze a foe. Mediocre. Actually not a lot of things are immune to being dazed and this ability scales according to your hit dice and your charisma modifier; unfortunately, you have to find a sneak attackable evil creature and use both of the special attacks in a single blow in order just to qualify to activate this ability. Still, some builds, for instance, a Shadowbane Inquisitor build, could find it to be a great addition to their arsenal. 
Devoted Performer CV: Paladin and bard levels stack for determining smite evil damage and number of bardic music/day. Unfortunately your bard songs do not get stronger by this feat alone, so you should also consider coupling this feat with Initiate of Milil which does exactly that: stacks your paladin, bard and cleric levels to determine how powerful your bard songs are. 
Devoted Tracker CV: Paladin and ranger levels stack for determining your wild empathy bonus and smite evil bonus damage. Also you can designate your special mount as your animal companion and gain both benefits. This is the base feat that is used in builds that are generally referenced as "supermount" or "ubermount"; this is because, by stacking the benefits of an animal companion (generally the one gained from the Ranger class won't do the trick - the animal companion gained by the Beastmaster CV is used instead) and your special mount. The Halfling Outrider CW and the Wild Plains Outrider CV classes are used to continue advancing both your animal companion and special mount features and gain an extremelly powerful mount - it's possible to have a companion with more than 20 hit dice if Unearthed Arcana bloodlines get into the mixture. You can add feats like Exalted Companion BoEDor Dragon Steed DrN for some additional special mount options.

Exalted:

Gift of Grace BoED: Share with your companions some of your divine grace. Not particularly useful.
Hands of a Healer BoED: Not exactly worth a feat. You can buy a wondrous item to the same effect.
Holy Radiance BoED: Shed light and deal damage to undead. Average.
Nimbus of Light BoED: Gain bonuses when interacting with good creatures and shed a bright light.
Nymph's Kiss BoED: You gain bonuses to charisma related checks, +1 bonus on saving throws for spells and spell-like abilities. Also 1 bonus skill point per level.
Quell the Profane BoED: Requires resounding blow. If the creature fails the fortitude charisma based saving throw, it takes 1d4+1 strength damage.
Resounding Blow BoED: If you hit deal a critical hit with a weapon you are proficient, he must succeed on a charisma based saving throw. If he fails he cowers for 1 round. Great, but you need 7 ranks in intimidate.
Sanctify Martial Strike BoED: Deal more damage to evil creatures, evil undead and evil outsiders. Also good aligned for overcoming damage reduction. Unfortunately it requires weapon focus.
Sanctify Weapon BoED: When you cast sanctify weapon, it also becomes sanctified. It deals more damage to evil beings. Corrupted creatures cannot recover lost hit points from a sanctified weapon with normal healing.

Special Mount:

Celestial Mount BoED: It would be better to use the planar level substitution than taking this feat. Nevertheless if you can't for some reason, it's still worth the feat.
Winter's Mount FB: This is worst than celestial mount even though it boosts its constitution.
Dragon Steed DrN: You gain a dragonnel as a special mount.

Initiate:

Initiate of Arvoreen CoV: Add hide and move silently to class skills and some spells. If you have the skill points to spend go for it. Unfortunately you can't get the Shadow Cloak Knight substitution levels, because they're only available to gnomes.
Initiate of Baravar Cloakshadow CoV: Great spells added to your list.
Initiate of the Holy Realm CoV: Bad ability and spells added.
Initiate of Horus-Re CoV: The wild shape ability can fulfill the requirements of prestige classes. Spells are bad though.
Initiate of Milil CoV: Great for multiclass bard/paladins. You need to get perform as a class skill though (through smite to song or able learner probably.)
Initiate of Nobanion CoV: Too narrow. Bad.
Initiate of Torm CoV: The smite ability is also too specific and the spells are even worse.

Skills

Standard Paladin Class Skills:

Concentration: Not particularly useful to you, unless you are planning to be casting spells in battle. However since you will focus on high AC it will pretty difficult to disrupt your spell even then. That is true, but even then, most of your combat spells will be swift action buffs, which you don't have to use concentration for, anyway. Invest in this only if you want to meet a certain requirement - many feats and prestige classes require concentration ranks. 
Craft: This is a skill for peasants, not charismatic leaders! Actually, the craft skill is more useful than I thought it would be. First of all, you can cut down on costs for armor and weapons, which requires pretty low difficulty checks. Then, since you're able to cast spells you can actually make alchemical items, too. Investing many ranks beyond those required for making some standard equipment is not recommended though, since intelligence is a dump skill for this class. 
Diplomacy: I'd max out this one. It gives you a lot of social interaction choices and with your high charisma you should be the party's face.
Handle Animal: I'd skip this one unless you would like to act as an animal tamer. There's no reason to spend more than a few ranks in this skill (in order to qualify maybe for requirements). There's no reason to not be an animal tamer - with a mild investment in the handle animal skill you can generate some really powerful allies, especially early on in your career, that can serve you as mounts, too, if you chose to swap your own for something else. 
Heal: Great skill to stop your fallen allies from dying. I wouldn't bother investing more than a few ranks, just to be able to make the check if need be. Some feats that have a healing theme require a few ranks in this skill. 
Knowledge (Nobility and Royalty): Get this at least to five ranks to gain the synergy bonus on diplomacy checks.
Knowledge (Religion): Spend five ranks in this skill so that you get the synergy bonus, which is great for any character who turns Undead. Synergy bonuses are great, but don't expect that you'll be turning or rebuking Undead creatures effectively, unless you choose to spend some cash on equipment that will enable you to do so. This is still ranked blue however, because it's your one and only skill that identifies creatures, which is important, especially if no one in the party can act as a monster identifier. 
Profession: Again this isn't a skill for a legendary commander. Actually not that true; there are several good choices here that fit thematically with the paladin class, for instance, you could be a captain, so it'd be great if you also had some profession(sailor) ranks; profession(sailor) by the way is one of the rare professions that also have a mechanical aspect - some spells from the Spell Compendium use profession(sailor) and it's useful if you're in a naval adventure. This skill is still ranked red, because it's more of a issue related to your character's theme, rather than optimizing your character.  
Ride: Max this if you plan on acquiring the mounted combat feats.
Sense Motive: Spend some ranks in this one. It can be used to identify the intents of NPCs you might come across and also has various social uses. Plus it gives you a good synergy bonus. 

Variant Paladins and Paladin Substitution Levels Skills:

Paladin of Freedom: As with standard paladin but diplomacy is replaced with bluff. Bluff is a nice skill. Spend at least 5 ranks in bluff as it gives synergy bonuses to four different skills.
Paladin of Slaughter: As with standard paladin but diplomacy is replaced with intimidate. Since you have a strong charisma, you can use intimidate to optimize stacking of fear effects.
Dragonborn Paladin: As with standard paladin but add knowledge (arcana) to class skills. I wouldn't bother with knowledges except if you need them for requirements.
Half-Orc Paladin: As with standard paladin but replace diplomacy with intimidate. Since you do this replacement only on the substitution levels, you won't have enough ranks to do a huge difference, but the investiture is worth it.
Elf Paladin: As with standard paladin but add survival to class skills. Don't bother.
Planar Paladin: As with standard paladin but add knowledge (The planes) to class skills. I wouldn't bother with this type of knowledge.
Crescent Moon Knight: As with standard paladin but add knowledge (local-impiltur) to class skills. Insignificant.
Holy Judge: As with standard paladin but add knowledge (The planes) to class skills. I wouldn't bother with this type of knowledge.
Lion Legionnaire: As with standard paladin but add knowledge (nature) to class skills. Leave this to more wilderness related characters.
Mystic Fire Knight: As with standard paladin but add knowledge (arcana) and spellcraft to class skills. Spend some ranks in spellcraft in order to get practiced spellcaster.
Noble Heart: As with standard paladin but add survival to class skills. Can't make a huge difference.
Ruby Rose Knight: As with standard paladin but add bluff and perform to class skills. This are nice skills to spend ranks, but the substitution levels suck.
Red Falcon: As with standard paladin but add knowledge (history) to class skills. Only useful if you have levels in bard.
Wary Swordknight: As with standard paladin but add listen and spot to class skills. Nice if you need to pay more attention to your surroundings.
Harmonious Knight: As with standard paladin but add perform to class skills. Again this is a nice skill, but the substitution levels are below average.
Shadow Cloak Knight: As with standard paladin but add hide and move silently to class skills. You already get bonuses to these skills for being a gnome and the substitution levels are great. Since you gain hide in plain sight, consider spending some points in these skills.

and finally you can replace some of the skills through Skilled City Dweller:

Replace handle animal with gather information: This is a useful trade. Gather information will see a lot more play from your part than handle animal.
Replace ride with tumble: Not so useful unless you give up your special mount. Even then, you will be wearing heavy armor and dumping dexterity, so don't expect much from this.
Replace Knowledge (nature) with Knowledge (local): Knowledge (nature) is gained through substitution levels. You may want to replace it to fulfill requirements.
Replace survival with sense motive: This is obviously a bad trade since you already have sense motive as a class skill.

Skill Tricks:

Dismount Attack: If you succeed in a fast dismount attack, you can attack an adjacent opponent as if you have charged him. Requires ride 5 ranks.
Healing Hands: Stabilize a character and heal them 1d6 hit points, which may make them functional again. Requires heal 5 ranks.
Never Outnumbered: Demoralize a group of enemies. Requires intimidate 8 ranks.
Social Recovery: Reroll a failed check to improve NPC attitude.

Equipment

Armor/Shields

Armor is important for a paladin. Your dexterity will be low, so this is the main way of boosting your AC. Typically paladins are figures in shiny metal armor.

General Enhancements:

Fortification (DMG): Negate critical hits and sneak attack damage to yourself will help your companions. Also improves survivability a lot. +1/+3/+5 bonus
Ghost Touch (DMG): Ghost ward is better. +3 bonus.
Undead Controlling (DMG): You won't be rebuking undead easily, so this is a quick way to get them to follow you. Later you can bend them to your will. +49.000.
Anchoring (MIC): Provides with nice bonuses to resist special combat maneuvers. Great enhancement. +1/+2 bonus.
Aporter (MIC): Nice ability since your mobility will be hindered.
Commander (MIC): Give some small bonuses to your allies. The bonus on the will saves is morale, so it will stack with most other bonuses. Only +2.000.
Ghost Ward (MIC): Most useful against those who hunt incorporeal creatures, this is a priority. Your flat touch AC will make you vulnerable to those creatures' attacks. +1 bonus.
Speed (MIC): 3/day create a haste effect on you. +6.000.
Fearsome (DotU): Gain bonuses to intimidate and demoralize as a move action.

Shield Enhancements:

Animated (DMG): Use a two handed weapon while taking benefits from a shield, too. +2 bonus.
Bashing (DMG): Specially designed for those warriors that prefer to use their shield as a weapon. +1 bonus.
Time Buttress (MIC): Become invulnerable to nearly everything for 1 round once per day. Powerful and flavorful. +5 bonus.

Armor Enhancements:

Agility (MIC): Reflex saves will be lower than the others usually, since dexterity isn't that important for you. This can help boost it a little. +500/+4.000/+8.000.
Blurring (MIC): The greater version of this can be activated any number of times per day and its duration is nice. +1/+2 bonus.
Buoyant (MIC): Negate the armor check penalty on swim checks. Along with your strength you will most likely manage to survive if you fell in a large body of water while wearing armor. Get it if you are going to adventure frequently near the sea, rivers, etc. +4.000.
Called (MIC): Donning a heavy armor tends to take a lot of time (donning a full plate takes some minutes). With this ability you can don your armor as a standard action. Also you can leave it anywhere on your plane and just call it back to you. +2.000.
Magic Eating (MIC): Your saves are already high, this extra bonus for a small price can be helpful. +10.000.
Menacing (MIC): Standard action to activate a charisma based fear aura. +30.000.
Roaring (MIC): Protects against ranged attacks and gives a bonus to initiative checks. Both are weak areas for paladins. +3 bonus.

Armor Crystals:

Crystal of Screening (MIC): You impose a penalty to the touch attacks of incorporeal creatures. If you are dealing a lot with them, you should get this since your touch AC will be crappy. +400/+1.000/+3.000.
Iron Ward Diamond (MIC): Damage reduction until it has blocked a certain amount of damage a day. +500/+2.000/+8.000.
Restful Crystal (MIC): Sleep in your armor without problem.

Weapons

There is two types of fighting styles commonly used by paladins:

Two handed weapons: Most of the times they are used in conjuction with power attack feats, resulting in good damage outputs.
One handed weapon along with a shield: More defensive capabilities and decent damage if you choose the right weapons.

What you will choose as your favorite weapon won't be really affecting your play a lot, so you can choose according to your personal style. Paladins have proficiency with almost all weapons.

Enhancements:

Bane (DMG): A bane weapon against the enemy you will most be facing can be helpful. Some types that can help include outsiders (good, evil, lawful, chaotic) and undead. +1 bonus.
Ghost Touch (DMG): Nice for ghost hunters, unfortunately grabbing a truedeath crystal is strictly better. +1 bonus.
Holy (DMG): Makes weapon good aligned for overcoming damage reduction and deals an extra 2d6 points of damage to evil creatures. +2 bonus.
Unholy (DMG): Ditto. +2 bonus.
Banishing (MIC): Banish creatures back to their home planes. Synergy with other weapon properties. +2 bonus.
Binding (MIC): Bar creatures from extra dimensional travel. Interesting if you deal with a lot of outsiders. +1 bonus.
Blessed (MIC): Treat weapon as good aligned and activate it to automatically confirm critical threats if you feel that you are feeling lucky (it's a swift action). +1 bonus.
Brutal Surge (MIC): After attacking, spend a swift action to initiate a bull rush. Usable 1 + constitution modifier. +1 bonus.
Charging (MIC): When you are mounted and wield this weapon, you deal an additional 2d6 points of damage on a charge attack. +1 bonus.
Dispelling, Greater (MIC): 3/day greater dispel magic as a free action. +2 bonus.
Divine Wrath (MIC): Spend a turn attempt to deal +1d6 points of damage per charisma modifier to undead. It's a divine feat for only +1 bonus.
Mighty Smiting (MIC): Bonus on smite attempts and one extra charge per day. +1 bonus.
Sacred (MIC): Bonus damage to undead and align weapon to overcome damage reduction. +1 bonus.
Stunning (MIC): Nice abilities, but why not take sudden stunning? +1 bonus.
Sundering (MIC): Allows you to attack as if you had the improved sunder feat. That has a lot of extra uses and you even deal bonus damage on sunder attempts. Great since you effectively gain a feat for only +1 bonus.
Warning (MIC): If your dexterity score is low, this comes handy if you don't have the feats to spend to improved initiative. +1 bonus.
Sudden Stunning (DMG II): Charisma based difficulty class that stuns a target. Usable charisma times per day. +2.000.

Weapon Crystals:

Crystal of Return (MIC): Especially the least one, gives you free quick draw for the weapon attached. 300/1.000/4.000.
Fiendslayer Crystal (MIC): Overcome damage reduction, deal extra damage and prevent the creature from using teleport. 1.000/3.000/5.000.
Truedeath Crystal (MIC): Great against undead. Extra damage, ghost touch and deliver sneak attacks or critical hits to undead. 1.000/5.000/10.000.

Miscellaneous

Belt of Magnificence (Miniatures Handbook): This is a must. Reduces MAD and makes you better in many areas.
Boots of Striding and Springing (DMG): A bonus to your land speed and jump checks.
Circlet of Persuasion (DMG): +3 competence bonus on charisma based checks.
Ioun Stones (DMG):
Pale Green: Bonuses to pretty all rolls.
Orange: +1 caster level, which is indeed needed.
Bead of Karma (DMG): +4 caster level for 10 minutes. Use it when you buff up.
Amulet of Retributive Healing (MIC): 3/day heal yourself for the same amount you heal an ally. 2.000.
Amulet of Word twisting (MIC): Nice bonuses to social skills you are going to use much. Also bigger bonuses for orcs. 6.000.
Armbands of Might (MIC): Nice bonuses to power attack and strength related skill checks.
Belt of Battle (MIC): Many uses and offers extra mobility and attack power. 12.000.
Belt of Growth (MIC): Increase in size, which results in bonus strength and reach. 3.000.
Boots of Battle Charger (MIC): Nice charging bonuses. 2.000.
Caduceus Bracers (MIC): Convert lay on hands healing to other modes and remove special conditions.
Circlet of Mages (MIC): Bonus to concentration and retain spells of various levels if charges are spend.
Reliquary Holy Symbol (MIC): Bonus turn attempts for only 1.000.
Strongarm Bracers (MIC): Wield larger weapons than normal. Nice for optimizing your damage output at low levels. 6.000.
Unicorn Pendant (MIC): Your charisma is considered 4 points higher for using your lay on hands ability. Also it boost even further your divine spirit's spirit of healing.
Veil of Allure (MIC): The difficulty class of enchantment spells or spell-like abilities as well as extraordinary and supernatural abilities is increased by 2.

Base Classes Dipping Guide

Bard: Opens up possibilities such as initiate of milil, devoted performer which result in interesting builds. Bards boost your reflex and will saves and give you access to arcane spells. Thus you can activate bardic wands and eternal wands.
Cleric: Probably one level of cleric is the single most powerful dip of all. Gives you turn undead earlier so you can acquire feats quickly.
Fighter: Sure, bonus feats are nice, but fighter levels hurt too much in paladin builds: Spells, caster level, class skills (although you do get intimidate in return), smite evil progression, turn undead, lay on hands, special mount. I don't think that getting one or two feats in return is worth it.
Monk: All good saves, but lots of monk abilities work only in light or no armor. One possibility is Ascetic Knight, taking one or two levels in monk and getting high unarmed strike damage.

1 level: Improved Unarmed Strike, Stunning Fist. I wouldn't take improved grapple as a paladin, stunning fist has some synergy with high wisdom. Also its difficulty class is based on character level. Also trade flurry of blows for Decisive Strike, a PHB II alternative class feature which unlike flurry, works in armor.
2nd level: Evasion, which works in light armor, so you should wear the best mithral medium armor (breastplate probably) and a bonus feat to either combat reflexes or Deflect Arrows. Don't take this level if your fighting style isn't two-handed. Deflect arrows which is the natural choice, works only if you have a free arm, which isn't the case with shield/sword. Also evasion is more limiting than helpful (since it limits your armor and you have to beef up your reflex saves).

Ranger: If you are taking this consider it closely. All stats will be important to you, will no exception. Devoted Tracker will stack paladin and ranger levels, resulting in powerful mounts.
Sorcerer: Charisma synergy, but gish builds with paladin levels, aren't actually paladin builds.
Wizard: Great with sword of the arcane order.
Hexblade (CW): Charisma synergy and will save boost. Curses won't see much play, but arcane resistance, mettle and the variant feature dark companion are nice.
Marshal (Miniatures Handbook): The minor auras use charisma modifier for the bonus they provide. This is great for field leaders.

Prestige Classes:

 Emissary of Barachiel BoED: The bad news are that the Words of Creation feat from the same book, is listed as a requirement; that feat is awesome, especially for bards, but it unfortunately requires you to have a score of 15 in your intelligence and a base will saving throw of +5, so dipping is almost certainly guaranteed in order to get in the class early. Fortunately, Emissaries of Barachiel do not have other difficult entry requirements to meet - only Diplomacy at 8 ranks (you should actually max diplomacy out with this class) and another, rather useless feat. What you're getting from this prestige class is just a single ability, called Calling, which is usable once per day per class level, just like bardic music; actually the whole class is probably intended for bard class. This ability is a powerful one, or should I say a game-breaking one, so, if you don't want books thrown at you, you'd better seriously consider taking this class beforehand. What makes this ability so good is that the saving throw difficulty class to resist the ability's effects is a skill check - more specifically you Diplomacy skill check (if you scroll back to the skills section you'll find out that Paladins have two skills that give synergy bonuses to diplomacy and that a single level dip in the Marshal class from the sourcebook Miniatures Handbook not only gives you +2 to your base will saving throw and the Motivate Charisma minor aura, but also a free Skill Focus[Diplomacy]!). And one would thought that if you have such a high-DC ability, well, the effect would be either too specific or too limited; well, you can use it to buff allies and debuff enemies, by applying them different conditions, based on their alignment. Those conditions are: Inspired, Blessed, Enthralled, Disheartened, Stunned and Demoralized, but the ability does not have a single target - it instead affects anyone within 30ft of you; yes, that's right - you can have inspired allies (+2 morale bonus to pretty much every roll for 10 minutes) and Stunned (1 round) AND Demoralized  (-2 to pretty much every roll for 10 minutes) by spending just one of the Calling ability. Wait, the list does not end here, when you reach level 3 you're able to freakin slowly convert creatures to lawful good - fortunately the Calling ability is [Language-Dependent, Mind-Affecting]. On top of that, the class gives you more skill points that the paladin class and even has Use Magic Device as a class skill; plus you get the ability to cast charisma-based spontaneous divine spells. 

Fist of Raziel BoED: This prestige class does not have the power to end campaigns like Emissary of Barachiel, but it does have very strong special abilities. First of all, you do get a permanent Magic Circle against Evil, which helps a lot versus summoned creatures and mind control, while giving you additional defenses against evil creatures, which are obviously your natural enemies, being lawful good. The prestige class features a lot of improvements to the smite evil attacks and it even offers more smite attempts per day and at a faster rate.   

Blackguard (DMG): poison use, sneak attack, Dark Blessing, but requires cleave and five ranks in hide to enter. If you use the variant evil paladins to enter, it can create a saving throws monster.
Cavalier (CW): Give up spells for mounted benefits. Continues special mount progression.
Halfling Ourider (CW): Another prestige class for special mount. This is actually better than cavalier but you need to be a halfling.
Hunter of the Dead (CW): Easy requirements. Great against undead. If you are in an undead heavy campaign, this is a nice choice. Unfortunately, even though hunter of the dead gives several turn undead features, such as divine feat-like abilities, it hasn't turn undead progression, so that means that you would probably use turn attempts to power divine feats and abilities.
Knight of the Chalice (CW): This is a very good class. Grants various immunities to you and allies, a turn undead feature that works against evil outsiders and some nice spells that aren't on the paladin's spell list. The knowledge (the planes) requirement can be achieved without spending cross class skill ranks if you take one of the substitution levels that add it to your class skills (e.g. planar paladin).
Holy Liberator (CD): Great abilities and you maybe can keep you paladin abilities with the variant paladin of freedom. Break enchantment is awesome.
Pious Templar (CD): Nice abilities and saves, mettle, spells and bonus spells. Also usable with all paladin variants.
Shadowbane Inquisitor (CV): Nice in conjuction with shadow cloak knight.
Vigilante (CV): The skill requirements are steep but with some substitution levels anr/or skilled city dweller you can get them on time. Gets nice features and arcane spells from the bard list.
Wild Plains Outrider (CV): Easy requirements and nice if you are going for a mount build.
Gray Guard (CS): Drop spells a little for the ability to smite anything and the ability to operate a bit unconventional.
Dragon Devotee (Races of the Dragon): Easy to enter, bonus feats, all stat boosts are to important ones, arcane spells and a free template, all in a nice package.

Special Mount Abilities

All of these abilities depend on paladin's level.

Bonus Hit Dice: The mount gets extra hit dice. These levels result in extra hit points, BAB, skill points, feats.
Natural Armor: A boost to natural armor.
Str Adj.: Bonus strength to your mount.
Int: Improvement to your mount's intelligence.
Empathic Link: Communicate with your mount from a distance.
Improved Evasion: As per the special ability.
Share Spells: This is very good. Effectively you are buffing two for one spell.
Share Saving Throws: Your mount can use your own base saves instead of its own.
Improved Speed: A bonus to the mount's speed.
Command: Your mount can command others of its kind.
Spell Resistance: The mount gains a lousy spell resistance.

Normally your mount will have the animal type. Animals get:

d8 hit dice.
3/4 Base attack bonus.
Good fortitude and reflex saves.
2+intelligence modifier skill points.
Low light vision.
Proficient with natural weapons.

There are however other ways to acquiring mounts:

Leadership: You can designate your mount to be a cohort.
Drakkensteed Mount: Gives you the choice to ride a drakkensteed. Drakkensteeds are dragonblood animals who fly. Unfortunately if you choose one as a special mount, they can't command others of their kind.
Dragon Steed: Gain a dragonnel as a special mount. Dragonnels are of the Dragon type, which results to full base attack, all good saves and many skill points, but you must treat it with additional respect.
Planar Paladin Substitution Level (6th): Your mount acquires the celestial template. Celestial template provides full base attack, better hit dice and darkvision.
Devoted Tracker: Lets you designate your animal companion as your special mount, which results in really powerful combinations.

Feats for Mounts:

Iron Will (PHB): Bonus to the mount's worst save.
Power Attack (PHB): Trade attack bonus for extra damage.
Improved Bull Rush (PHB): Nice for bull rush attempts and requirement for awesome blow.
Run (PHB): Useful in non combat situations.
Track (PHB): Again, have your mount do the tracking if you need one in your party.
Ability Focus (MM): +2 difficulty class to the special ability of your mount.
Awesome Blow (MM): Nice if used with a bonus to damage (such as the celestial's smite).
Flyby Attack (MM): Move and take a standard action at any point during the move.
Improved Natural Armor (MM): +1 to your mount's natural armor.
Improved Natural Attack (MM): Bonus damage is always nice.
Draconic Aura (Dragon Magic): If your DM is ok with it, you can get this with your Drakkensteed (which is dragonblood). Saving a feat and providing bonuses to all your party.

Builds 

PHB only: Paladin 20 

1) Power Attack, Bonus) Improved Sunder, 3) Mounted Combat, 6) Ride-By Attack, 9) Spirited Charge, 12) Trample, 15) Improved Overrun, 18) Leadership

Max ride skill.

The Mystra's Chosen: Human Paladin 6/Gray Guard 9/Witch Slayer 5
Takes the mystic fire knight substitution levels at 5th and 6th paladin level.

1) Power Attack, 1) Dreadful Wrath, 3) Improved Sunder, 5) ACF - Divine Spirit, 6) Divine Might, 9) Sacred Healing, 12) Divine Vigor, 15) Sacred Vitality, 18) Leadership

Charisma synergy, it is used for:

Saves
Damage
Turn
Lay on Hands
Divine Spirit
Smite (also extended smite from mystic fire knight)
Fast Healing
Leadership
Momentary Disjunction
Dreadful Wrath

Books:

PHB
DMG (Leadership)
Complete Scoundrel (Gray Guard)
Complete Warrior (Divine Might, Divine Vigor)
Compete Divine (Sacred Healing)
Dungeonscape (Divine Spirit)
Libris Mortis (Sacred Vitality)
Player's Guide to Faerun (Dreadful Wrath)
Champions of Valor (Mystic Fire Knight)
Tome of Magic (Witch Slayer)

The Undead Hunter: Human Paladin 5/Hunter of the Dead 10/Paladin +5:

1) Power Attack, 1) Improved Sunder, 3) Sun Devotion, 5) ACF - Divine Spirit, 6) Sacred Vengeance, 9) Awesome Smite, 12) Extra Turning, 13) Spurn Death's Touch, 15) Sacred Vitality, 18) Leadership

PHB
DMG (Leadership)
Complete Warrior (Hunter of the dead, Sacred Vengeance)
Complete Champion (Awesome Smite, Sun Devotion)
Dungeonscape (Divine Spirit)
Libris Mortis (Sacred Vitality)

Chameleon Way Paladin: Human Paladin of Freedom 5/Chameleon 10/Witch Slayer 5:

1) Able Learner, 1) Nymph's Kiss, 3) City Slicker, 4) ACF - Holy Warrior, 4) Power Attack, 5) ACF - Charging Smite, 6) Divine Might, 7) Floating Feat, 9) Awesome Smite, 12) Divine Vigor, 15) Sacred Vitality, 18) Leadership

BAB 17.
Great saves.
This actually reduces MAD due to bonus chameleon stat points.
Bonus feat can be used to take a divine feat you want to use earlier.
Max UMD.

PHB
DMG (Leadership, Power Attack)
Unearthed Arcana (Paladin of Freedom)
Complete Warrior (Divine Might, Divine Vigor)
Complete Champion (Holy Warrior, Awesome Smite)
Dungeonscape (Charging Smite)
Races of Destiny (Able Learner, City Slicker, Chameleon)
Libris Mortis (Sacred Vitality)
Tome of Magic (Witch Slayer)