You are a proponent of DMs (and only DMs) framing scenes since you worry that the players may frame themselves into easy situations or with easy obstacles to overcome
Correct.
yet you trust the paladin player to adjudicate his own actions when it comes to his code. Why don't you share the same concerns when it comes to the paladin, since he is in essence (through creating his own code, deciding the gray areas of the code, and having the ability to ignore it if he truly wants) also choosing whether a moral obstacle or scene is weak or strong
To me this seems to be quite different.
Any obstacle is an obstacle only relevant to a motivation. In technical terms, a "scene" expresses a hypothetical imperative: if you want to achieve X, then you are going to have to overcome Y. My concern about players framing scenes is that they will squib when it comes to specifying what Y is. Hence I prefer GM authority with respect to Y. But when I frame a scene, I am taking for granted a particular value of X.
For instance, in my most recent session the PCs were trudging through the icy tunnels of the Shadowdark, on the far side of the Soul Slough, heading for Torog's Soul Abattoir where they hope to destroy the Abattoir and defeat Torog. En route they were attacked by a beholder death emperor and the Worm of Ages. Thus, the hypothetical syllogism was framed: if you want to get to the Soul Abattoir, you must overcome the death emperor and the Worm. (This is the basic structure for all romatnic quest stories, I think.)
But the scene I've framed is only a challenge if the value of X is held constant. If the PCs decide to give up on Torog and the Soul Abattoir, then they don't have to overome the death emperor and the Worm: they can just run away back to their waiting planar dromond, and on their phantom steeds they have a better movement speed than either of those monsters. Part of the skill of GMing in a non-railroad but non-sandbox style is having a sound intuition on what "X" is for the players (this is "the GM being hooked by the players"), and this is why games in this style use devices - formal or informal - so that the players can tell GMs what "X" is for them.
The paladin's code is one value of, or one component of, "X" for the paladin player. Given that value of X, I as GM can fairly easily frame a moral challenge.
If the player changes, or has changed, that value of X - ie what s/he takes his/her PC's obligations to be - then a scene that would have been a challlenge may not be. But that is no more an issue for GMing a paladin then for GMing any other PC. If the player of the fighter decides s/he no longer cares what the king thinks of his/her PC, then the delicate negotiation scene that I framed may turn out not to be a big challenge after all!
Handling these changes of X - which naturally occur from time to time as the game is played and PCs evolve - and reading those changes, whether expressed formally or informally, and responding to them in a flexible way, is another GMing skill. Sometimes it turns out that X has changed faster than the GM anticipated, and what was intended as a challenging Y turns out not to be. Or perhaps the nature of the challenge changes - here is an example from actual play:
The PCs in my 4e game were raiding a goblin stronghold (the Chamber of Eyes from H2) and while the goblins fell back and regrouped, the PCs ducked into a small room to take a breather. They found themselves in the room of a couple of duergar slave traders, who had been keeping their heads down during the fighting.
The module author certainly assumed that if/when the PCs encountered these duergar, a fight would ensue. And that had been my default assumption also. But on this particular occasion the players were fairly low on resources (hence they had decided their PCs would take a short rest) and they also didn't feel any special animosity towards the duergar. So the scene went in a different direction: the PCs negotiated with the duergar to redeem the slaves for an agreed price on an agreed date in a nearby town. (Resolved as a skill challenge.)
That's an example of X changing, or at least turning out to be something different from what I as GM anticipated, and the nature of the Y therefore also changing in a flexible way. I haven't found GMing paladins to raise any special problems in this regard.
Burning Wheel, which has a formal technique for the signalling of X by players - namely, Beliefs - also has a rule that a player may change a Belief at any time, but that the GM may delay the implimenation of a change of Belief if s/he thinks it is being done simply to wriggle out of a difficult situation that the GM has framed for that player and his/her PC. Because, in D&D, there is no comparably formal system, there is no corresponding formal power in the GM to stop the player squibbing. In my own play, if I feel that the player is not really feeling the force of the moral challenge of the Y in the way s/he is playing his/her PC in response to it, I (verbally) poke and prod the player, perhaps making comments like "What would Moradin think?" or reminding them of some grievance they've been nursing from some earlier episode of play - in other words, informal techniques for the GM corresponding to informal signalling of "X" by the players. (Those informal techniques may seem obvious - I personally didn't work them out myself, though, but learned them from an excellent GM running a Cthulhu freeform at a convention in Melbourne in 1992.)
I am under the assumption that anyone who makes a character has a story they want to tell.
<snip>
The GM sets up challenges and based on the type of story the players want to tell, they interact with them. I assumed this was the normal way people played RPGs, it's certainly been my experience.
I see this as being in the same general neighbourhood of my Xs and Ys above: the player has some desire or goal for his/her PC, and the GM frames challenges that must be overcome if that goal is to be realised.
As GM I will discuss the Xs with the playes as part of campaign set-up, post-game reflection etc - that is part and parcel of everyone being on the same page with the game - but during play it is the players who have authority over the Xs, and what counts as satisfying or thwarting X. My job is to keep piling on enjoyable Ys.
I have no problem separating myself from my character and judging my character based on the actions taken. (it is the player judging the characters actions, not the character judging his own actions).
<snip>
Nothing for me is more immersion breaking than a GM imposing himself on my character. He should present challenges that put the character's morality and ethics to the test, but the internal results of those challenges, when it comes to the character, should be left to the player who better understands the morality of the character himself
This all works for me. I also agree with your account of "narrative" consequences - upthread I think I've used the phrase "story consequences".
One of my assumptions - building on your idea that "anyone who builds a PC has a story they want to tell" - is that the players, having built a PC with goal X,
care about X as an element of the unfolding fiction. Hence they will care about "narrative consequences" like (for instance, in my game where the paladin turned on the heavens) angels and the like no longer treating them as friends/allies.
I know this is not true for all RPGers - some prefer a "step on up" sort of game where the main action is in the accruing of XP and treasure, and the story element is mostly just a flavour context for play - but for my techniques to work for me they don't have to be applicable to all RPGing at all times and places - just for me and my group!
one of the classic (as in, found in the source material that inspired the class) challenges of playing a Paladin- the risk of losing one's divinely granted boons if/when one goes against the tenets of one's faith or violated their vows- becomes, in a sense, optional.
And that just doesn't feel...right.
In one sense it's always optional, in that it requires someone to make a decision that is not forced upon them. The question currently at issue is whether that will be the player or the GM - and a secondary question is whether that should lead to a signficiantly reduced mechanical effectiveness for the PC (I don't see why it should - after all, other players who spurn the gods don't therefore get stuck with less mechanically effective PCs - hence my preference for blackguard conversion rules, even if they are a little cartoony as written).
But being a paladin, cleric, etc. is about accepting the moral tenets of something or someone else and following them.
I don't involve the deities directly, nor do they have any direct influence on the game itself. When I run games I don't "play the deity."
I do involve the deities directly in my game, but I take it for granted that if one of the players is playing a cleric or paladin of that deity then I am not the only one who has a stake in that NPC. Just as if I bring a PC's parent, or hometown, into play, the player of that PC has a stake in that too.
So, for instance, in my 4e campaign more than one of the Raven Queen worshippers has met with and interacted directly with their god, played by me as an NPC - mostly in the course of being resurrected - but that doesn't mean I assume I'm at liberty to have her do whatever I might feel like, including stripping them of their abilities based on an adverse moral judgement.
I see this as a special case of a more general principle - that in certain mechanical situations the GM does not have sole authority over NPC behaviour. So, for instance, if the game involves morale rules, and the NPC fails a morale check, then the GM is obliged to honour that. Or, if (as in 4e, for instance) the game has social resolution mechanics, and the players by dint of those mechanics extract some concession or favour from an NPC, then the GM is not at liberty to just disregard that (any more than s/he can just disregard a damage roll against an NPC's hit points during combat) - s/he is obliged to honour that.
So in the case of a god, or a PC family or hometown, the player has automatically acquired a stake in that simply by dint of PC creation. And as a GM I am obliged to honour that.
That's not to say I can't test it. For instance, the invoker/wizard in my game has an imp familiar, who is a watcher sent by the arch-devil Levistus to keep tabs on him. I can use this set up to push and prod that player, and even to contribute to the framing of a challenge - but in the final analysis the player bought that imp familiar with PC build resources, and so I don't have licence just to competely rob the player of his familiar and have it turn on him because "that's what Levistus would do". Levistus and his imp servants are no longer my sole property in the game.