You have to understand there are two "locks" that people talk with phones. First is the SIM card lock. This is a lock that prevents you from changing to another service provider. Most service providers will place this type of lock on your phone if you are purchasing the phone on an installment plan. If you buy it outright, or bring your own phone, then it either won't be SIM card locked or they will remove the lock upon request.
The second type of lock is the "boot loader" lock. Every new phone will come with this lock activated from the factory - even those sold as "unlocked". This prevents someone from loading any unauthorized software/OS on the phone. However if your phone is sold as "bootloader unlocked" then you should be able to turn this lock off in the phone's settings. Doing this will factory reset your phone but it doesn't require that you actually install a new OS. It just gives you the option to install something else in the future if you want to. Of course you can leave the option locked and only unlock it when you are ready to install something.
Verizon has consistently blocked their "Verizon" model phones from have the ability to unlock this bootloader. This means that any "Verizon" specific phone will never be able to have the bootloader unlocked even if the manufacture makes non-Verizon models that can be bootloader unlocked. The Google Pixel phones are a good representation of this. You can buy an "unlocked" Pixel phone that will work on Verizon and allow you to unlock the bootloader if you choose, but if you buy the Verizon model of a Pixel phone, it will be permanently bootloader locked and you will never be able to install custom ROMs or similar software on them.
Another thing to keep in mind is that the phone generally has to be SIM card unlocked before you can unlock the bootloader. For example, if you buy an AT&T model Pixel phone on installment plan through AT&T, you will likely have to pay the phone off and get the SIM card lock dropped before you will be able to bootloader unlock the phone - even though the phone is designed to allow you to bootloader unlock it. This is to prevent people with a locked SIM card from simply unlocking the bootloader and installing software that would bypass the SIM card lock.
If you buy one of the "Unlocked" Google Pixel phone models, it will come from the factory without a SIM card lock and you'll have the option/ability to unlock the bootloader should you decide to. This is probably the best option for anyone considering rooting and/or installing other software on their phone. And yes, you can take any of the Pixel phones and use them on the Verizon network.
Hopefully that helps.....
I have not personally tried the GrapheneOS on my phone, but I am mildly interested in trying it out. I used to unlock and root all of my phones going back at least a decade, but I stopped doing that with my last two Pixel phones. I just didn't have a compelling enough reason to unlock and root the phones.