Just my 2 cp, but i think giving paladins Smite Points or something like that wouldn't be a half bad idea myself. Letting them use the points for smiting, turning, or auras. I think that would work great, must the same way i like how rage points work for barbarians. Yes, we could give everyone points, but i dont really like that idea, but i do like the flexibility it would give paladins.
I do think paladins should get Detect Evil. Its something they've always had, though it tends to be abused. I think its a classic feature that needs to be preserved, if modified somehow.
I also do not think paladins should be something other than LG. If you want a non LG paladin, make a cleric =P Or take blackguard prestige class.
*Edit* And yes, i very much think paladins should be Charisma casters. They represent the martial leaders of the church and their deity. And because of that spark, their god takes notice of them. I think that is more personality than wisdom based. *Edit*