If I were your player, I'd probably be a mounted charger of some sort. Invest in Mounted Combat/Spirited Charge and a lance. I'd start by riding around on a Magebred [ECS] Mule at level 1, since I couldn't afford a horse. I'd upgrade my mount when possible, probably using the Warbeast template [MM2].
Keep Power Attack, but shift it to level 3, when it actually makes more of a difference (it's not very good without multipliers and with only 1 BAB), ditch Monkey Grip. I can wield a two-handed weapon just fine without it. Battle Blessing [CC] is a good idea once I can cast spells. I'll also grab a flaw, since paladins don't get any bonus feats. Charging Smite [PH2] instead of a special mount at level 5. The special mount is good, but so is charging smite. Since I'm using warbeast animals anyway, charging smite it is.
So.
Human Paladin 1
Maxed Skills: Handle Animal, Ride, Concentration, 3 others
Str 18, Int 16, Wis 16, Dex 8, Con 17, Cha 17
Starting gear (assuming average wealth of 150gp. After purchases, 38gp 1sp 7cp remain): Magebred Mule (16gp), Lance (10gp), Dagger (2gp), Club (0gp), Spiked Studded Leather Armor (75gp), 2x Waterskin (2gp), Backpack (2gp), Flint and Steel (1gp), 10x Chalk (1sp), 10x Candle (1sp), Bedroll (1sp), Winter Blanket (5sp), 3x Torch (3cp), 3x Day's Rations (3gp)
The spiked armor is so that you threaten at normal range. The dagger and club are alternate damage types in case you run into skeletons or zombies or similar. Your main attack is the lance, wielded 2-handed from the back of your mule, for an attack of +7, hitting for (1d8+6)*3 [21-42dmg] at level 1.
Feat progression:
Level 1: Mounted Combat, Ride-by Attack, Spirited Charge
Level 3: Power Attack
Level 6: Animal Devotion
Level 9: Battle Blessing
Level 12: Sword of the Arcane Ordeahahahaha who am I kidding I don't know anything about paladins