Você habilitou a descompactação automática conforme informado na documentação?
HttpClientHandler httpClientHandler = new HttpClientHandler();
httpClientHandler.AutomaticDecompression = DecompressionMethods.All;
HttpClient httpClient = new HttpClient(httpClientHandler);
var api = new CepApi(httpClient, httpClientHandler);
Obrigado pela ajuda. Era isso que estava faltando, a descompressão.
Achei estranho pq já uso o serviço a quase um ano e nunca tinha dado esse problema.