OK, I’ve had a chance to review my notes and other related materials. And they reminded me that the Nazgul’s power was primarily in the spiritual world, not the physical world. Physically they weren’t all that intimidating; they couldn’t see well, didn’t hear so good, didn’t like to cross water, and were somewhat dependent on their companion animals (horse, fell beast, etc) to navigate, at least in daylight. They inspired terror and couldn’t be slain by any ordinary weapons, but were hard-pressed to interact with the physical world in the first place. Which is why the goal of the Nazgul on Weathertop was to stick Frodo with the Morgul blade, driving him into the spirit world, where they could dominate him.
Given that description, it would seem to be a wonder that the Witch-king of Angmar was such a threat to the Numenoreans, eventually causing the downfall of Arvedui, last king of Arnor. And also responsible for the end of the line of Anarion too. But it seems WK did this thru his spiritual powers rather than the physical; dominating and directing his underlings and terrifying his foes, a la his master Sauron.
And as for how the WK got so powerful by the time the Battle of Pellenor Fields rolled around; well keep in mind that on a physical plane he still wasn’t that overwhelming physically. He was trying to kill Eowyn with a mace, after all, not crushing her physical existence with a flick of his fingers. Powerful yes, but not overwhelming. And his physical power was perhaps enhanced by being the focus of Sauron’s eye, being given more strength via his master. His best feature in battle was that no man could kill him.
As for the battle with Gandalf, their battle would have been much more on the spiritual plane, had it taken place. And while Gandalf was a maiar who had defeated two other maia already, they had all been limited in some fashion; Gandalf and Saruman by the constraints of their physical bodies and the limits imposed on them by the powers when they became istari. The Balrog had been diminished over ages by spending his power in terror and hate, a la his master, Melkor.
So in the spiritual battle, you’d get a somewhat constrained maia vs. a corrupt mortal spirit supported by a stronger maia drawing on the residual power of a downcast Vala. Anything could have happened! (But I still would not have bet against Gandalf. I bet he would have overcome the WK, but would not have been able to destroy him. And I gravely doubt Gandalf would have been physically destroyed by the WK.)