Confesso que andei nos últimos tempos tentando estudar isso do ponto de vista um pouco mais prático. Acho que a questão é compreender a separação entre o que é o software e o que é o serviço do Google.
Conversas do WhatsApp e do Facebook não são necessariamente sincronizadas com (a conta d)o Google, a menos que você deixe o backup ativado.
Mesma coisa para os contactos, aí na print eu mostrei as opções que me aparecem, mas pode ser que no meu caso eu esteja em uma versão mais antiga.
Considerando-se que nem sempre instalar um sistema alternativo é uma opção (seja pela falta de ROMs, seja porque o procedimento viola a garantia do aparelho), o que pode fazer, e dado que algumas aplicações podem não funcionar adequadamente com o microG, uma alternativa pode ser desabilitar todas as aplicações do Google com exceção do Play Services e da Play Store.
Por um acaso desses acabei achando esta suíte de aplicativos de código aberto e que respeita a privacidade dos seus usuários, inclusive ela conta com um aplicativos de contactos, pode ser uma alternativa para o colega, ele desabilita o Contacts do Google e usa essa no lugar:
https://simplemobiletools.github.io/