Deveria começar pelo Android, substituindo pelo GrapheneOS.

Antes de comprar, veja se o celular escolhido possui ROMs prontas para ele, caso ele seja muito novo ou muito esquecido, você não encontrará muita coisa. Nesse caso você teria de limpar os bloatwares. Os bloatwares são todos aqueles apps que ocupam espaço e não servem pra nada, por exemplo, você não usa a câmera do celular, pra que então ter o app? Desinstale-o.

1 - Graphene OS

2 - Calyx OS

3 - Lineage OS

Essas são as principais e mais comuns ROMs voltadas para privacidade.

Na hora de instalar a ROM, não instale gapps (nenhum mesmo, se quiser algo da google, não estará sendo privado o suficiente), e depois de instalar, verifique apps que você não precisa e remova-os usando ADB ou Shizuku + Canta.

Lojas de Apps:

Obtainium

Aurora Store

Zapstore

Accrescent

Droid-ify

Remova tudo que pede KYC, remova tudo que quer saber como você usa seu celular, remova tudo que usa mais permissões do que o necessário. Procure alternativas open source para cada app que você usa.

Whatsapp? SimpleX

Twitter? Amethyst

Instagram? (Pra que você precisa disso?)

Bancos? Carteiras de Bitcoin

Youtube? Odysse, PipePipe

Google? Foss Browser, Iron Fox, SearXNG

A lista é grande, procure no perfil do nostr:nprofile1qqsyh28gd5ke0ztdeyehc0jsq6gcj0tnzatjlkql3dqamkja38fjmeqpr9mhxue69uhkummnw3ezu7n9vfjkget99e3kcmm4vsq3camnwvaz7tmwdaehgu3wvf5hgcm0d9hx2u3wwdhkx6tpdsqs6amnwvaz7tmwdaejumr0dsmgvaqu, tem bastante coisa sobre o assunto.

Ideal seria usar SOs como GrapheneOS e CalyxOS, porém eles estão limitados a hardwares muito caros, como um Pixel para GrapheneOS, cuja versão mais "em conta", Pixel 7, perderá suporte ao SO a partir de 2027. Um celular sem hardware proprietário é essencial, pois SOs que dependem do Android acabam tendo esse mesmo problema, o ideal seriam celulares como Librem, Fairphone, mas não são muito acessíveis em questão de preço, e sistemas operacionais como PureOS ou Mobian. Quanto apps, que foi a pergunta principal, isso vai depender um pouco de que celular e SOs foram escolhidos, eu uso um celular comum, então me limitarei a isso:

Mensageiro: SimpleX Chat

E-mail: Tutamail (não acho essencial ter e-mails, ideal é nunca usar coisas que exijam login, mas sei que nem sempre é possível)

Roteamento: Orbot

Loja de app: F-droid, Zapstore

Browser: Tor Browser

Nenhum app de código fechado seria aceitável

Não sei qual seu objetivo e qual uso daria a um celular focado em privacidade total, porém seria bom se fosse para atividades mais voltadas a uso limitado, como é o caso de usar Tails só para usar Electrum, do que para uso cotidiano. Eu acho que não vale a pena, estou cada dia mais usando meu pc e usando celular só quando sou obrigado.