Yesterday I started a softcore Paladin on US East called ACS_Poet.
Yeah, I know Pallys suck, but I just like them.
He's probably going to focus on Vengeance and Charge as his main attacks, while flashing a few auras. I'm thinking Fanaticism (maxed), Holy Freeze and Redemption (both low base level, boosted by +skills items).
20 levels in Vengeance, Charge and Fanaticism = 60 levels.
Let's say 5 base levels each in Freeze, Redemption and Holy Shield = 15 levels
Total = 75 skill points, plus a few for reqs.
That should do, I don't intend to level him up to 99 (he's sub-optimal anyway, so Hell difficulty will be harder than usual).