I'd like to note that I'm not necessarily concerned with backwards compatibility here. I'm just trying to bring some material for thinking about for all the knights in shining armour hanging around.
I know that it's still not the right time, but when there are so many threads discussing retardedness of certain abilities of the Paladin class, then there may be one more.
I think we should pay some attention to his spell casting abilities. I think it certainly isn't nice to hear jokes that a paladinis actually a cleric who's antenna to gods was misalligned by a glancing blow during combat training and so he was given a sword and sent to do good somewhere else (which would explain the nonexistence of paladins with different allignment, their deities lacked the compassion needed to do this and kicked them out without the shiny sword).
Enough fun
The paladin in it's basic kit is equipped with a modest amount of spells for as long as I can remember (not THAT long actually), But I think that you'd agree with me that I won't be far from truth if I say about his spells that they came too late, and they did too little to help (not all).
I already suggested elsewhere that a Paladin should be able to cast his spells (those with standard action casting time) as a swift action, so that he can boost himself while swinging sword, which would definitely improve his performance in combat. The other thing I'd like to have a look upon would be paladin's spell list.
The Panadin starts to receive his spells at level 4 and I think it's safe to assume that under most circumstances he won't even receive 2 bonus spells from his wisdom (there are other, more pressing needs for high ability scores for paladins). So I think that there won't be any protests if I include some more powerful spells from cleric list of appropriate level (power level, not spell or class level) and make it more oriented toward fighting evil.
1st-level paladin spells
Useful (I can see Paladin having these prepared often)
Bless, Detect Poison, Divine Favor, Magic weapon, Protection from Chaos/Evil
Use-impaired (Not ofthen memorized. Some are on list just to allow the paladin to use appropriate magic items... those who don't want paladin to cast spells probably overlook this use)
Bless Water, Create Water (I'd leave these for Cleric, but create water may be there to make up for usually poor survival skill)
Cure Light Wounds (With all the healing paladin gets from other sources...)
Detect Undead (Is it really worth the effort? You have Detect Evil and one or two slots of this level for most of your career, so I doubt that anyone would actually take this)
Read Magic (I'm still not sure whether this shouldn't be left out anyway. I don't like to see everyone casting whatever he wants with scroll at hand, but sometimes the resurrection is far, far away)
Lesser Restoration (Prepared only after the need arises)
Useless
Endure Elements (I think that most paladins would rely on their superior saves and proper clothing to handle the weather)
Resistance, Virtue (Even if the paladin had the scrolls I doubt that he'd bother to use it)
Possible Additions (Not tested or anything...)
Aid, Calm Emotions, Entropic Shield, Gentle Repose, Light, Mending, Shield of Faith
2nd-level paladin spells
Useful
Bull's Strength, Eagle's Splendor, Resist Energy, Shield Other
Use-impaired
Owl's Wisdom (The only real bonus is the increase of will save, which can be had through Divine Grace boosted by Eagle's Splendor as well. Paladin spells rarely need to have higher save DCs)
Remove Paralysis (Prepared when needed, I doubt that most Paladins have a condition specific spell like this ready)
Undetectable Alignment (Too sophisticated to be in general use)
Zone of Truth (Too sophisticated to be in general use, I'm not sure whether this shouldn't be left to Clerics)
Possible Additions
Align weapon, Cure Medium Wounds, Make Whole, Magic Vestment
3rd-level paladin spells
Useful
Daylight, Dispel Magic, Magic Circle against Chaos/Evil, Greater Magic Weapon, Prayer
Use-impaired
Remove Blindness/Deafness, Remove Curse (Prepared when needed, I doubt that most Paladins have a condition specific spell like this ready)
Useless
Cure Medium Wounds (should be moved to 2nd level)
Heal Mount (Could be replaced with other healing)
Possible Additions
Cure Serious Wounds, Divine Power, Freedom of Movement, Sending, Spell Immunity, Water Breathing/Water Walk
4th-level paladin spells
Useful
Break Enchntment, Death Ward, Dispel Chaos/Evil, Holy Sword
Use-impaired
Mark of Justice (Not a combat spell = not prepred at all times)
Neutralize Poison (Use specific)
Restoration (not needed that often and it could be lower level or placed within LoH uses)
Useless
Cure Serious Wounds (should be moved to 3rd level)
Possible Additions
Cure Critical Wounds, Disrupting Weapon, Raise Dead, Righteous Might, Spell Resistance, True Seeing