I highly recommend GrapheneOS on a Google Pixel. You can also get a used one, just make sure to buy a Pixel 6 or newer, as the models don’t get security updates anymore. The Pixel 6 is supported until October 2026 (~3 years). You can check out the entire list of supported devices and the minimum support length on this site. Pixels are a fantastic choice for security because of their Titan M security chip which has support for various Android security features like the Weaver API which throttles unlock attempts making brute-force attack unfeasible, Android StrongBox, and Insider Attack Resistance.

GrapheneOS is really awesome, by default it doesn’t include any Google services making it an excellent choice for privacy. You can install Google Play services, but they will run in a sandbox, you have the ability to restrict what Google has access to on your phone. They also make significant security improvements like hardening the memory allocator, the C library, SELinux policies, etc. What makes GrapheneOS so much better than other ROMs is the fact that you can relock the bootloader and make use of Android Verified Boot with GrapheneOS’ custom signing keys.

You can watch this video or read the official documentation to learn more. My advice: Stay away from insecure ROMs like LineageOS.