So what would the solution for Android phone be? Buy a new Android phone or buy an iPhone? They are very similar from the perspective of your data being owned by the phone OS maker.
I thought one of the big selling points of IPhone vs Android was greater privacy protection, and the fact that Apple's business model isn't based around selling user data? There's also the possibility to use a de-Googlified version of Android like https://lineageos.org/.
After extensive research, this was ultimately my conclusion: Going iOS. My rationale was that it is significantly easier to de-Google an iPhone then it is to de-Google and android phone. I can also lock down an iPhone more easily (Disabling iCloud, using DNSCloak, etc).
There are plenty of projects that aim to remove Google from an android, but I question their security; even if the privacy is good, there could be exploits or unpatched vulnerabilities.
This comes with a price: the cheapest iPhone SE costs 3-4 times more than a new low end Android phone and 2 times more than a decent Android phone. An iPhone 12 is more than the average monthly pay, so in price-sensitive markets (or price-sensible in the common sense way) going iOS is out of reach for most people.
There are a few linux phones now. None are ready for prime time yet, but all are close. Contribute to development (either by writing code, or just funding it) and they will be sooner. I'm excited about the pinephone, but there are a few others.