I think the "set spell list" plus Advanced Learning thing is really a good way to go for every caster, Arcane or Divine. You automatically get everything a caster of your type is expected to have to fill your role, and you get to choose a few extra spells to better define your role, fluff, and abilities to your own personal idea of the character.
Paladins, for instance, should have a short list of spells, and a few Advanced Learnings. Maybe 1 per spell level, or something (I think the rates in existing casters need to be sped up, but probably also that they need to lose some spells off their auto spells-known). Clerics might get a reasonably extensive list, based on a number of archetypes, and then 1 spell known each class level.