Web crawler that uses Task Parallel Library
From MSDN on Task.Wait:


  If the current task has not started execution, the Wait method
  attempts to remove the task from the scheduler and execute it inline
  on the current thread.


I have a feeling that something similar might be happening with WaitAll, killing performances. I'll have a look and see if I can find documentation about it. As you are using StartNew some of the tasks might be started already so they won't be in-lined.

I would refactor it using async/await so you are sure you are not using and blocking only one thread from the pool:

async static Task&lt;IEnumerable&lt;string&gt;&gt; GetAllPagesLinks(IEnumerable&lt;string&gt; rootUrls, bool hostMatch, bool validatePages)
{
    var result = await Task.WhenAll(rootUrls.Select(url =&gt; GetPageLinks(url, hostMatch, validatePages)));

    return result.SelectMany(x =&gt; x).Distinct();
}

static async Task&lt;IEnumerable&lt;string&gt;&gt; GetPageLinks(string formattedUrl, bool hostMatch = true, bool validatePages = true)
{
    var htmlDocument = new HtmlDocument();

    try
    {
        using (var client = new HttpClient())
            htmlDocument.Load(await client.GetStringAsync(formattedUrl));

        return htmlDocument.DocumentNode
                           .Descendants("a")
                           .Select(a =&gt; a.GetAttributeValue("href", null))
                           .Where(u =&gt; !string.IsNullOrEmpty(u))
                           .Distinct();
    }
    catch
    {
        return Enumerable.Empty&lt;string&gt;();
    }
}

async static Task&lt;IEnumerable&lt;string&gt;&gt; GetLinks(string url, bool hostMatch = true, bool validatePages = true, int level = 0)
{
    if (level &lt; 0)
        throw new ArgumentOutOfRangeException(nameof(level));

    string formattedUrl = FormatAndValidateUrl(url);

    if (string.IsNullOrEmpty(formattedUrl))
        return Enumerable.Empty&lt;string&gt;();

    var rootUrls = await GetPageLinks(formattedUrl, hostMatch, validatePages);

    if (level == 0)
        return rootUrls;

    var links = await GetAllPagesLinks(rootUrls, hostMatch, validatePages);

    var tasks = await Task.WhenAll(links.Select(link =&gt; GetLinks(link, hostMatch, validatePages, --level)));

    return tasks.SelectMany(l =&gt; l);
}


Haven't had a chance to test it, but just get the gist.