Qual é a melhor maneira de substituir a parte do host de um Uri usando o .NET?

Ou seja:

string ReplaceHost(string original, string newHostName);
//...
string s = ReplaceHost("http://oldhostname/index.html", "newhostname");
Assert.AreEqual("http://newhostname/index.html", s);
//...
string s = ReplaceHost("http://user:pass@oldhostname/index.html", "newhostname");
Assert.AreEqual("http://user:pass@newhostname/index.html", s);
//...
string s = ReplaceHost("ftp://user:pass@oldhostname", "newhostname");
Assert.AreEqual("ftp://user:pass@newhostname", s);
//etc.

System.Uri não parece ajudar muito.