As others have stated, grapheneOS is a good choice, and it's extremely secure.

Another option is murena' eOS. If you live in Europe, thier store sells phones with the OS preinstalled, and if you don't, the easy installer app works pretty well with most models.

But fair warning, I recently installed eOS on my wife's old Samsung S7, and I ended up having to do the installation manually with adb (command line tools). So read up on the phone you want to use, some are easier than others.

The operating system itself is great, and allows for anonymous usage of the play store (free stuff only of course) as well as F-Droid out of the box. You can also add your Google account to get full play store functionality, but then Google starts getting your info again, albeit less than with standard android.

If you are looking for a generic phone with good privacy and usability I would highly recommend a Pixel with Graphene OS. If you've never flashed a phone before, you can install Graphene within a web browser and never need to do any of the more complicated flashing stuff like most other setups require. It also allows you to optionally install Sandboxed Google Play Services (on the main profile or isolated on a second one), letting you access normal apps while still having some of the privacy and performance benefits of an otherwise de-Googled phone.

Graphene OS
CalyxOS
Lineage OS

Those are the big three players in alternative operating systems that I know of. I use Calyx because my threat model is corporate data collection more than absolute security. Ironically, the best phones to put these operating systems on are the Google Pixel line because you can unlock and lock the bootloader. I'm not sure if there are other phones that allow this but the websites of the OS should guide you to hardware.

The issue is that easily unlockable bootloaders exist, it’s just that they exist on [Shady Company] Pixels. So you either move on to a privacy focused OS and lose a bunch of basic ass features because [Shady Company] slowly removed them from the main OS, or you end up using the least privacy focused device ever made in the history of humanity. So if you’re just in it for the basics, iOS is the way to go. I’m telling you this as someone who has been rooting, buying and selling Android devices for about 9 years.

The internet is forever and there is no privacy on the internet.

As others have said, the Pixel line is the easiest if you want to have full control over the phone.

There are others, but it will take more effort to get there (I say this after flashing and rooting all my phones since 2010).

Take a look at lineageos.org/devices to see what devices they support, it's a good approximation of which phones can be boot loader unlocked.

After lots of looking around, I decided to finally jump to Pixel, and I'm running DivestOS (a fork of Lineage with a little bit more tweaked, like sandboxing MicroG).

Once you decide to go down this road, I'd suggest downloading the factory rom image for your phone, and practice flashing it, before trying with a custom rom, just so you have some experience with a known-good image. Plus, sometimes you have to flash back to stock - I just did one the other day because I screwed up the custom rom flash.

If you're just looking for the out-of-the-box experience, I'd say a Pixel is probably your best bet. It'll run stock Android, get updates the fastest, and generally perform very well. My Pixel 6 Pro is still running smoothly today. I've never dived too deeply into it, but I believe Pixels will also run GrapheneOS, if you're looking to really lock your device down and de-Google it.