This thread, has, I think, some of the best responses of any thread I've ever seen on this site.
I wish I could give experience points to many of the responses, but I need to spread some more around.
Not much more I can add in this case but from my point of view, and having played a Paladin, I'd just say that a Paladin can be, and often should be, in conflict between the various points on his own (as well as the world's) motivational compass.
There should be inherent conflicts, from his point of view, or anyone's point of view who tries to operate in the world striving to do the best and most noble and most honorable thing, yet who is also not nearly naive enough to think that the best and most noble and honorable thing is the way the world actually often operates.
There should always be a real conflict between Intention and Reality.
And this is especially true with a Paladin who strives to achieve an Ideal but must actually operate in Reality.
He should be at conflict between True Goodness and Real Justice, as opposed to temporary necessity and human law, he should be at conflict between Personal Honor and Self-Sacrifice, and Service to Others, and Survival.
This is what I think makes the Paladin actually one of the most interesting Character Types/Professions to play.
How will his personal ideals, his innate spiritual values, his duty to society and those he serves, his immediate goals and objectives, his higher motivations, and his own personal character be tested at any given moment in any particular situation, and then how will he resolve those conflicting concerns in the best way possible?
Personally I am, as a DM, not in favor of demanding too harshly or rigidly that the Paladin resolve every situation and every conflict in the same way on every occasion. The Paladin should not be, in my opinion, a "moral relativist" by any means, but then again he must fight the enemies he actually encounters, and strive to change the world for the better as he actually discovers the world, not as he wishes it to be.
And sometimes that can be a very difficult thing, both in fiction and in fact (real life). And it can be a very rewarding set of conflicts to actually resolve (if you can - and everyone fails from time to time), but it can also be an extremely taxing and even grief-filled set of circumstances to have to actually endure.
So good luck with it, but in my opinion being a Paladin is not a set of rules you follow in place of your soul, they are a set of rules and guidelines you follow to try and discipline your soul and thereby use that self-inflicted discipline (physical, mental, and spiritual) to help improve the world around you.
So being a Paladin, or anytime you set out to become something greater than yourself, will actually make you more yourself, not less, and becoming a Paladin should make your character far more multi-dimensional and more truly himself, than not.
A Paladin can and should be many things, but he should never be a caricature of himself. Rather he should be a man filled with real character. Hard won and well disciplined character.