I think with the game as it is today it's best to do some along the way. If you get to 62 with 0AA's you're going to be hurting. People expect you at that level to at least have some. It also depends a lot on your play style. If you're in a small family oriented guild and aren't a power gamer it's best to take your time. If you want to be in an uber guild you usually need to level up faster.
Other factors play in. I often see people recommending not to level up till they have all their spells for that next level. Or they say to get AA's as you can get groups no problem even if you're 59 in stead of 62. Most of these people are casters. Level mitigation comes into it big when you're trying to get a group as a tank. Most groups will instinctively take a higher tank, thinking they will take a better beating.
Honestly, there is no easy answer. I can tell you that I quit the game at one point because I was concentrating on levelling up and falling behind on AA's and finally got frustrated. I think the best course for most paladins these days is to do it in stages. Concentrate on levels till 55-56 or so, then get some AA's. Not necessarily a lot, but maybe at least the first round (run3 regen/metabolism usually) and then maybe a few defensive. Perhaps the first of CA,CS. Then maybe level up to 60 and finish out defensive AA's, and maybe grab that Holy Steed that every paladin wants. Then level up to 65 and get a few more, etc.
In the end, it's all up to how you want to play. You can argue efficiency all day, but if you're not having fun, what's the point?
____________________________
Some people are like slinkies, they aren't really good for anything, but they still bring a smile to your face when you push them down the stairs.