A Paladin gets a temporary (once per day for only a few rounds) Holy Avenger with the Holy Sword spell at level 15. That is a fun spell to use and is quite good. Therefore I wouldn't give a Holy Avenger to the character until at least 16 so that they would have some time to play with their new spell and enjoy it. Once you get a HA, Holy Sword will probably never be chosen again (and that is probably the single best Paladin spell there is). Of course, Complete Divine finally added a few spells that could also be fun to play with.