It's not so much underestimating them as looking at a one-on-comparison with Numenoreans in general, and appreciating his ability to triumph when adding the power of a Nazgul and likely lacking any sort of holy blessedness.
The man who would be the fifth of the nine was the greatest of the heroes to ever emerge from the windswept plains of Khand. His people, the Variags, were mercenaries in theory only — for one master alone they could not refuse, and though the pay was great and lavish, his hand was terrible over them. A captain there was among them, a man who had journeyed to the Far East where the sun scorches the world as she sinks, who had toasted dead men in the sunless halls of Haben-Harath and learned the art of the sword-dance from the elves of the East. He had fought for Númenor and for Mordor and for kings and masters of which Sauron and the Tall Men alike had never heard, and he returned home with a strange and wonderful idea: Freedom.
The Variags rallied around him, for his wagons were high with wealth and splendor, and moreover there was a thunder in his voice that could move hearts. For longer than their stories stretched the power in Mordor had had it's hand over them, and for longer than memory their sons had marched west to suffer for the Dark Lord. But were the ever-glorious Variags of Khand not the mightiest of all the warriors of the world, he said? Did the tall men out of the sea not cry out in fear at the sight of their banners on the wind? Were they not famed in the deeps of the Harad and the far reaches of the world? Why should they, the conquerors of all the earth, tremble and shake before the Eye?
From east to west he rode and his voice was like a torch and in his wake all the realms of Khand rose in fire after him, and many of the Easterling tribes as well — among them the dread Khundolar and the fearsome Bharath. By time rumor had reached Mordor of dissent in the east, he was already hailed as king, and armies marched to his beck and call. With all his other captains occupied in the west, Sauron sent forth the latest and cruelest of his Nazgul, Imraphor. A conqueror unmatched he had been in the Harad of old, a Captain of the armies of the Númenóreans, and the south-men had suffered terribly under his hand even when he was a man. Now he was dead without death, and his cruelties were multiplied hundredfold.
War came to Khand. They say that the king of the Variags readied himself long to face his foe. He took up a great shield of black iron, which had been forged by East-Elves on the shores of the great sea of Rhûn. He wrote his skin all over with words of power from far Harad, words to give a man the strength and heart of beasts. He armored himself in the great-armor of his people, which had been blessed by all the priests of all the cities of Khand, and donned a mighty helm wrought for him by the Dwarves of the Folk of Rhaz, who dwell under the Red Mountains in the sunlit lands. It had a hideous face carved upon the mask, and was laid with runes of protection and power. Last of all he took up his sword, which was a blade of Númenor, made in the days of her glory. The hilt was of mithril, and the spells that were on it were spells high and old for the ruin of the Enemy.
And at last, the King of Khand rode to face the host of Nazgul on the green plain of Nurn, and there was fire and death and thunder at their meeting. At the Ringwraith's fell voice, the army of men broke, and the orcs fell over them, and there was slaughtering and wailing, but in the blackest hour the Variag-King met Imraphor the Conqueror in battle, and his laughter shook the hills. Great was the skill of the king, and dauntless his heart, but his enemy was terrible, and wicked, and his eyes were a cold fire. Long they struggled on the battlefield, and his shield was cracked in ten pieces and his armor was rent from him by the strength of his foe, and even his terrible helm was cloven in two. But his sword was a blade of Númenor, made in the days of her glory, and the hilt was of mithril, and the spells that were on it were spells high and old for the ruin of the Enemy, and as it drove through his heart the Nazgul was undone.
The skies cleared, and the orcs wailed and wept and ran, and the mortal man stooped, and from the lifeless robes he took a golden ring.
That was nine hundred years ago.
The king of the Variags lives still. He bears a terrible helm reforged in the black pits of Mordor, and a shield of black iron remade by slaves and cooled in the black waters of the black land. His sword is a witch-blade of Mordor, made in the days of Sauron's glory, and the blade and the hilt and the crest are wrought of a nameless metal whose bite is as death. His voice spreads still through all the land of Khand, but now it is a voice of terror and woe, and men tremble to hear it. The numberless armies of the east march always before him — the dread Khundolar and the fearsome Bharath and at their head the ever-glorious Variags of Khand. He is merciless and terrible and his eyes burn with a cold fire.
He, alone of the Nine, remembers regret.