WebClient.DownloadString results in mangled characters due to encoding issues, but the browser is OK

It's not lying. You should set the webclient's encoding first before calling DownloadString.

using(WebClient webClient = new WebClient())
{
webClient.Encoding = Encoding.UTF8;
string s = webClient.DownloadString("http://export.arxiv.org/api/query?search_query=au:Freidel_L*&start=0&max_results=20");
}

As for why your alternative isn't working, it's because the usage is incorrect. Its should be:

System.Text.Encoding.UTF8.GetString()