[Boromir88]

Eyown showed no fear of the Witch-King, yet with one blow the Nazgul Lord not only shattered the shield of Rohan's Shieldmaiden, he broke her arm.

But you are comparing Eowyn to, as has been shown one of the mightiest Elves on Middle-earth. Eowyn though strong and brave, can be no way compared to Galadriel's power. Also, I never said that the Witch-King had no power over the fearless, the quote just says they had "no great power over the fearless," as opposed to those who did actually fear them.

Also, before you guys say anything about "social rank" leading to instant victory

Point taken, but "rank" certainly plays a significant role in the outcome. Sure elves can slay Balrogs, men can slay dragons...etc. In all those cases the people siezed a good oppurtunity to beat an opponent of greater strength. But, "social ranks" have a big effect on the outcome, because the majority of the time the greater power would win.

At the gate of Minas Tirith, Gandalf-who did not fear the Witch-King-doubted he could win.

I beg to differ...

'Then, Mithrandir, you had a foe to match you,' said Denethor. 'For myself, I have long known who is the chief captain of the hosts of the Dark Tower. Is this all that you have returned to say? Or can it be that you have withdrawn because you are overmatched?'
...
'Nay, I came rather to guard the hurt men that can yet be healed; for the Rammas is breached far and wide, and soon the host of Morgul will enter in at many points. And I came chiefly to say this. Soon there will be battle on the fields. A sortie must be made ready. Let it be of mounted men. In them lies our brief hope, for in one thing only is the enemy still poorly provided: he has few horsemen.~Minas Tirith

Denethor's words show more contempt and dislike towards Gandalf, sort of like "Oh, Gandalf you retreated...have you met your match then?" and Gandalf simply tells him no.
Then the actual encounter:

In rode the Lord of the Nazgûl. A great black shape against the fires beyond he loomed up, grown to a vast menace of despair. In rode the Lord of the Nazgûl, under the archway that no enemy ever yet had passed, and all fled before his face.
All save one. There waiting, silent and still in the space before the Gate, sat Gandalf upon Shadowfax: Shadowfax who alone among the free horses of the earth endured the terror, unmoving, steadfast as a graven image in Rath Dínen.
'You cannot enter here,' said Gandalf, and the huge shadow halted. 'Go back to the abyss prepared for you! Go back! Fall into the nothingness that awaits you and your Master. Go!'
...Gandalf did not move. And in that very moment, away behind in some courtyard of the City, a cock crowed. Shrill and clear he crowed, recking nothing of wizardry or war, welcoming only the morning that in the sky far above the shadows of death was coming with the dawn.~Siege of Minas Tirith

Gandalf shows no fear and is the only one to stand before the Witch-King...

Gandalf looked through the gaping Gate, and already on the fields he heard the gathering sound of battle. He clenched his hand. 'I must go ' he said. 'The Black Rider is abroad, and he will yet bring ruin on us. I have no time.'
'But Faramir!' cried Pippin. 'He is not dead, and they will burn him alive, if someone does not stop them.'
'Burn him alive?' said Gandalf. 'What is this tale? Be quick!'
'Denethor has gone to the Tombs,' said Pippin, 'and he has taken Faramir, and he says we are all to burn, and he will not wait, and they are to make a pyre and burn him on it, and Faramir as well. And he has sent men to fetch wood and oil. And I have told Beregond, but I'm afraid he won't dare to leave his post: he is on guard. And what can he do anyway?' So Pippin poured out his tale, reaching up and touching Gandalf's knee with trembling hands. 'Can't you save Faramir?'
'Maybe I can,' said Gandalf; 'but if I do, then others will die, I fear. Well, I must come, since no other help can reach him. But evil and sorrow will come of this. Even in the heart of our stronghold the Enemy has power to strike us: for his will it is that is at work.'

Gandalf is faced with a choice, to pursue the Witch-King in what seems like he's confident he can defeat him. He "must" go or others will die. He's faced with a choice, go after and kill the Witch-King, or save Faramir, he chooses the latter. Gandalf throughout the whole encounter shows no sort of second-guessing...plain and simple he could have mopped the floor with the WK.

Also seeing, so great was Galadriel's power that Lothlorien would only fall if Sauron himself came...