Assuming Uther's anti-demon/undead powers work on Nightmare, he's boned.
Pallies are custom made to beat down 'evil' entities. Problem is the concept of evil. The WoW universe has insane pallies like the Scarlet Crusade, and the Argent Dawn. These guys aren't necessarily totally evil, but they are fanatics and not necessarily good.
So by that logic, how can there be evil paladins? 🤨
And yes, Night Terror would probably eat Uther alive.
As for Arthas beating the Silver Hand? Well, if we take cutscenes as canon (and to some extent we have to), then he did kill Uther solo. It gets left aside alot, but Arthas wasn't a rookie. He was a spectacular paladin, the best in the kingdom. Uther was grooming him as his successor. And the Lich King made Arthas his personal champion with Frostmourne, which is one of the best blades in the WoW universe.