I agree that Paladins' should get extra Smite Evil attacks per day as they go up in level. That's why I like Divine Might so much. It's like a mini Smite Evil that you can get multiple times a day (though I think ultimately more useful, as it lasts for a number of rounds, rather than only good for 1 attack).
Anyway, I'm done. This is what I've come up with:
1st Aristocrat 1 Power Attack / Improved Shield Bash
2nd Paladin 1
3rd Paladin 2 Mounted Combat
4th Paladin 3
5th Paladin 4
6th Paladin 5 Divine Might
7th Paladin 6
8th Paladin 7
9th Paladin 8 Divine Shield
10th Fighter 1 Shield Expert
11th Fighter 2 Ride-By Attack
12th Paladin 9 Spirited Charge
13th Paladin 10
14th Paladin 11
15th Paladin 12 Leadership
16th Purple Dragon Knight 1
17th Purple Dragon Knight 2
18th Purple Dragon Knight 3 Extra Turning
19th Purple Dragon Knight 4
20th Purple Dragon Knight 5
He'll be a Paladin of Helm, so he'll be able to multiclass both Fighter and Purple Dragon Knight without any problems.
This is what I'm thinking background-wise. Started his life as a nobleman in Cormyr, but gave up all the trappings of nobility when he received the call to Paladinhood. So he joined up with the Cormyrean army and rose through the ranks. (Remember, I'm starting the character at 7th level)
He served til 1371 DR, when a red dragon led an army of orcs and goblinoids into Cormyr. (I need to read "Death of the Dragon" for this part of the background, so forgive me if I step on canon, but I'm making this part up based on bits I've heard from that book.) He took part in that war, and witnessed the battle between Azoun and the red dragon, and feels guilty that he couldn't do something, anything to save King Azoun.
So he left the Purple Dragons and travelled west, where he fell on hard times. During the course of which he loses his Paladin abilities (He didn't do anything that an Atonement can't fix. But while he can Atone, he doesn't feel worthy of becoming a Paladin again).
So when the other PC's find this guy, he'll be a broken down has-been. A tough and experienced warrior, but totally demoralized. As for what spurs him back into, action, well, that depends on the game.
But my goal is to eventually have this guy return to the Purple Dragons, where he gets elevated to the rank of Purple Dragon Knight (the Prestige Class) and sets up a castle somewhere along Cormyr's border to protect it. Helm is the deity of Guardians, Protectors, and Protection, and this Paladin of Helm will rededicate himself to defending Cormyr.
So how does that sound?