You are preparing Spells, using your intelligence, in order to be cast from paladin spell slots. <Class> Spells actually has no RAW definition, and so you have to ask your DM 2 things when you take it:
1: Do you have to buy the spellbook?*
2: What does he define <Class> Spells as being. If we are not overlapping definitions, the term means "Spells cast from Spell Slots granted by the given class". this lets you battle bless a few good wizard spells, and isnt really broken considering how the feat works. the entire first sentence of SotAO actually doesnt need to be errata'd
PrCs are mostly for focusing on only one aspect of paladin
There are 2 Anti-Mad options for paladin: Dragonlance's Dynamic Priest or Dragon Compendium's Serenity. These feats are keyed to charisma-ifying and Wisdom-ifying the paladin. Serenity is a bit better at base as it doubles Wisdom to willsaves, while Dynamic priest only shifts spellcasting's Required attribute and bonus spells to charisma.
Dynamic priest is also better for Bardadin builds, as you cant migrate Bardic Music from charisma.
This selection of whether your primary attribute is Wisdom or Charisma should heavily influence your choice of race.
*If your DM says yes, then you need to take a flaw to get the Magical Training regional feat, so you do have a spellbook.
Definitely keep an eye towards taking the Divine Spirit ACF, as it unifies paladin's abilities, and has the best healing in 3.5 (Crusader has to waste valuable maneuver choices to get good healing, paladins throw out a gimmick)