Android

Funnily enough some of the best phones to avoid google and improve online privacy are the google pixel phones.

GrapheneOS supports pixels and is regarded as the most privacy and security focused ROM atm.

Other options are vanilla builds of custom ROMs, which don't include gapps, LineageOS being the best known with the most amount of supported devices.

Another privacy focused, but less well known ROM is DivestOS which offers support for a good range of devices and allows for the bootloader to be relocked on some devices. The main Dev for this ROM is the same guy that develops the Mull android browser.

These are the ones I've had personal experience with but there are other out there like CalyxOS and /e/ that are marketed as privacy respecting ROMs but I have not tried these before.

Unfortunately, even though Android is open source, google likes to ensure that all android phone vendors include google play services with their phones. They do this by having most android apps integrate with google services for things like real time notifications.

If you choose to avoid google, some applications won't work properly such as banking apps and google pay and notifications for apps may not work properly either, there are ways around some of these issues such as microg and magisk modules but magisk requires root access which can make your phone less secure.

If you decide you want to install a custom ROM make sure the phone you have can unlock the bootloader, I don't think Verizon or other carriers allow unlocking the bootloader of the phones they sell, this is different to network unlocking, and right now there is no known way to unlock these phones bootloaders and the companies don't provide any support to do this.

So the best thing to do is buy directly from the manufacturer such as google. I don't have experience with Samsung phones but I know that they have their own security implementation which may limit the ability to unlock some of their phones but I'm not too sure. XDA forums are a good place to see what phones have custom ROM support and if the phones bootloader can be unlocked.

There are only really 4 ways to avoid google on your phone these days

1. No phone/ dumb phone

2. GNU/Linux based OSs such as Ubuntu touch or System76 phones

3. Custom ROMs without gapps

4. iPhone

The first 2 options aren't really viable for most people.

The 3rd option is my favourite and the 4th option is my worst nightmare