I bought an used Pixel and installed GrapheneOS in it. Highly recommended, I've had 0 issues related to it.
In my country (Colombia), phones cannot be carried-locked, so no idea in that regard.
Basically, all recent-ish Pixel are compatible, but Graphene devs recommend some bases on their support: https://grapheneos.org/faq#supported-devices and https://grapheneos.org/faq#recommended-devices.
Pixels are rather expensive, although not prohibitely. GrapheneOS's team is making a deal to bring the OS to another manufacturer, however, no idea how long it will take to 1) seal the deal, and 2) have a usable and stable GrapheneOS in it.
I've run SNES and GBA emulators on mine just fine.
The only kind of app I've known to cause troubles with GrapheneOS are banking ones. Mine work perfectly, but there is a crowdfounded status repository.
Overall, I think the consensus is that GrapheneOS is the golden standard in smartphone security+privacy (excluding Linux Phones, but they are not ready for average modern use). If you want to buy a new phone, go for Pixel with Graphene. There also exists LineageOS, Calyx, e/OS, which are not as good, but are way better than stock Android from Samsung, and have a waaaay bigger list of compatible phones, so maybe your current one will work.