Google's own Android phone line, recommended as the hardware base for a de-Googled setup because it ships with an unlockable bootloader, a Titan M secure element, and multi-year guaranteed security update commitments.
The phone you start with decides how private you can make it. A handful of devices give you an unlockable bootloader and strong hardware security, which together are the foundation for a de-Googled setup with a hardened mobile OS.
The two things that matter for a private setup are an unlockable bootloader, so you can install an alternative operating system, and modern hardware security like a dedicated secure element with long guaranteed update support. Together they let you run a hardened, de-Googled OS while keeping verified boot intact.
You cannot bolt strong privacy onto a phone that will not let you replace its software or stops getting security patches. Picking the right hardware up front is what makes a clean, well-supported alternative OS possible, instead of fighting a locked device the whole way.
Buy a supported device, then follow the install guide for a hardened mobile OS. If you would rather not flash it yourself, some vendors sell the same hardware with the alternative OS already installed and verified, ready to use out of the box.