Apparently this is a SO shortcut: but I came across this first, trying to figure this out myself before eventually finding the other 2 SO posts referred to below (2021 posts > 2013 posts, I guess).
Unfortunately, while .TryAddWithoutValidation in the originally accepted answer does seem to circumvent the issue on headers like Accept-Encoding, it will not work for others like Content-Encoding. For example, APIs like Salesforce Bulk API 2.0 will reject your request if you don't specify this header when Using Compression for uploading data.
Usage in the original post was the same as mine today, so I'm posting my workaround which was derived from https://stackoverflow.com/a/10679340 and https://stackoverflow.com/a/16959464/901156 indicating HttpRequestMessage.Content.Headers as the intended collection, not HttpRequestMessage.Headers.
For future reference, the correct implementation for using .Headers.Add(...) to add both of these headers would be req.Content.Headers.Add(...) not req.Headers.Add(...) for content-based headers, as demonstrated below (where I'm actually using their alias collections .ContentType and .ContentEncoding where they do exist; and not on their parent request object).
public async Task<AuthHttpResponse> AuthHttpRequest(HttpMethod method, string requestUri, byte[] data = null, string contentType = "text/csv; charset=UTF-8", bool enableCompression = true)
{
    using (var req = new HttpRequestMessage(method, requestUri))
    {
        req.Headers.Authorization = new AuthenticationHeaderValue(DefaultAuthenticationScheme, _authToken);
        if (enableCompression)
        {
            req.Headers.Add("Accept-Encoding", "gzip");
            if (data != null)
            {
                req.Content = Compress(data);
                req.Content.Headers.ContentType = new MediaTypeHeaderValue(contentType);
                req.Content.Headers.ContentEncoding.Add("gzip");
            }
        }
        else
        {
            if (data != null)
            {
                req.Content = new ByteArrayContent(data);
                req.Content.Headers.ContentType = new MediaTypeHeaderValue(contentType);
            }
        }
        var res = await _httpClient.SendAsync(req);
        res.EnsureSuccessStatusCode();
        string json;
        // Only decompress if server acknowledged
        if (res.Content.Headers.ContentEncoding.FirstOrDefault() == "gzip")
        {
            var buffer = await res.Content.ReadAsByteArrayAsync();
            using (var stream = new MemoryStream(buffer))
                json = await Decompress(stream);
        }
        else
        {
            json = await res.Content.ReadAsStringAsync();
        }
        return new AuthHttpResponse { Content = json, Response = res };
    }
}