Android/iOS will always have a chokehold on their users. The Librem 5 is a potential alternative, a Matrix-integrated and fully open source phone. Although it still has some rough edges to be ironed out.

F-Droid [1] has addressed this pretty well for Android devices.

[1]: https://f-droid.org/en/packages/im.vector.alpha/

Until F-Droid removes the app from the store for whatever reason

F-Droid supports adding additional repositories, so there is no "the store."

Where's my sledgehammer these days...?

This looks like a throwaway answer, but it's really the only right one: the only phone that offers privacy or anonymity is one that is smashed to dust. Anyone who is concerned for their security in any way beyond, "Hey, don't tell Jim, okay?," should never, ever use their phone, and I don't see a way to fix that. The makers of phone hardware, the software providers, and the service providers are completely unworthy of trust, and I can't see that changing.