I'm actually working on a paladin-esque fix, and what the code comes down to is, "don't tick off your god" with a stern warning to the DM of "don't be a dick" and quite a bit of fun roleplay and fluff to work on. So, an easy answer would be to have the player consider the god they're following, and what the god embodies. Go from there. Or start with a character concept, and have the player pick one or two virtues for their character to strive to embody, and a vice or two that also define the character's personality.
Example: Serilda Stormheart, Devoted of Raederic (I call my paladin fix the "Devoted"). Embodies: the virtues of mercy and justice, with the vices of hatred (in nicer terms, retribution) and tyranny (control). So Serilda strives to be merciful to creatures that deserve mercy, but struggles to not view the world in terms of good and bad. In action, she used non-lethal damage to stop a mob that was attacking the party because of an over-zealous, xenophobic preacher, but she is also capable of killing enemies without a thought for mercy when she feels that justice is better served by vengeance. And if she gets a chance to sneak attack or kill enemies who are unaware, she takes it. To do otherwise (especially since the lives of all humans are at stake in this campaign, but she would probably do the same if a smaller number were at stake) would be against everything she believes in, even if it isn't honorable.
That's my view of a paladin, at least. Not a knight in shining armor - though such a character is possible with my fix, too - but a complex character that has a moral compass and codes but regularly struggles with her beliefs.