public static string NewUrl(string url, Dictionary<string, string> query)
{
    var uriBuilder = new UriBuilder(url);
    var queryString = HttpUtility.ParseQueryString(uriBuilder.Query);

    // Aqui o objeto anônimo seria percorrido e então adicionaria
    // um novo parâmetro para a QueryString da URL AO INVÉS do dicionário.
    foreach (var q in query)
    {
        queryString[q.Key] = q.Value;
    }

    uriBuilder.Query = query.ToString();

    return uriBuilder.ToString();
}

NewUrl("http://example.com/?param1=abc", new Dictionary<string, string>
{
    { "param2", "12345" },
    { "otherParam", "huehue" }
}); // http://example.com/?param1=abc&param2=12345&otherParam=huehue

NewUrl("http://example.com/?param1=abc", new
{
    param2 = 12345,
    otherParam = "huehuehue"
}); // http://example.com/?param1=abc&param2=12345&otherParam=huehue