Ok, that's fair - if you want all of your paladins to be but holy warriors.
But how about we spin this idea, a D'Artagnan type of character?
Both father and mother could be ex-adventurers. Mother was a cleric of Sune and when she fell in love with father - a fighter and fencing master - they decided to settle down in a city. Mother decided to upkeep her faith by opening a bordello and father started teaching fencing. Character has both religious (mother - Sune) and martial (father - Fencing) upbringing. Character grew up among promiscuous people and maybe had a knack for artistry - helping bordello ladies put on make-up, learned how to sing and dance from the people surrounding her at all times. He/She held them in high regard for they were family. In comes times when bordello is shutdown and all ladies are put out of work. Comes in tyrant ruler who treats poor people like crap. Character can't stand for it, but has his own sense of morality and beliefs.
Oath of devotion:
Honesty - be honest to those who are your friends and family, do not ever sell them out or cheat them out of things.
Courage - stand up against the usurper and don't sit idly by while people you love suffer, voice your opinion and be angry if actions of people anger you.
Compassion - show acts of kindness to those less fortunate in the ways you know how and if a small lie can save beggars life why not do it?
Honor - do not fight dirty, keep your word and show your enemies mercy once they are beaten.
Duty - those people raised you and even if they are treated as low-lives by the rest of society you want to pay them back for all the good they did for you and nothing will stop you from doing so.
So if my character is a womanizer who likes to have a good time, sometimes throws silly one-liners at enemies, makes those who cheat look like fools, hangs out with promiscuous men/women and has a dream of opening up an establishment where people play cabaret he/she can't be a paladin?