2021: Braxman says older Pixels are now being unsupported by some US carriers (Pixel 1 and 2 are spotty for this)
Difference between Graphene and LineageOS, according to people online:
(Too many to list, but shorthand overview)
Graphene focussed on real security work, so for people who care about security, but is mostly just for Google Pixel phones of a few editions. Harder to mess up the security, for the regular nontechnical user. Supports verified boot. Can relock the bootloader after installing it. 'AOSP with more hardened privacy.' Now has sandboxed GooglePlay services if you want to use Play (still unstable). Community has been said to be a bit toxic (I have no first hand with this).
Lineage designed for powerUsers who want to tweak it and have bells and whistles, and is available for lots of phones. Targets support. Is effectively the same as flashing AOSP on an out-of-support ROM but less breakage. 'AOSP without Google.'
Calyx, a third OS people online recommend sometimes. Is fully deGoogled. 'AOSP with some additional privacy features.' Works only on Pixels (like Graphene).
If you want to use any of these, before you buy a phone make sure it has an unlocked OEM. Go to Phone and make yourself Developer, then go to settings and unlock OEM. If you can't unlock OEM, you can't install any of these.
Check if an app will work on a deGoogled device with https://plexus.techlore.tech/ On left is Graphene and on right is Calyx and Lineage. It is color coded for if it works.
These limit Google's ability to spy, and that ability for the companies who own any apps you might want to install. These still leave hardware vulnerabilities. You're still vulnerable to tracking by the carrier and government creeping. But you can remove or turn off physically the SIM modem.
Some have noted that tracking is so offensive to people because it's become so precise (6 feet). But if tracking is made less precise it offends people less, while allowing them to use geolocation for convenience (maps, finding locations near them). So if they can be located within a block or two, for example, it's less offensive than 6 feet.
Advantages of using a deGoogled phone over a LinuxPhone: Can use newer, faster phones. Can use all apps (compromising to various levels on your security/privacy).
The reason using a deGoogled phone is better even if you want some apps. Using the PlayStore means the apps use Google's code (connects to Google, even to get notifications for the apps I've heard, but also databases I've heard). A deGoogled phone, even if it connects to Google to use PlayStore, doesn't usually have an id (has a spoofed id), ie the owner doesn't sign in (it does get a device fingerprint and will know what apps the phone has installed from Play, but it won't have access to users financial records), and wifi scanning is disabled, limiting a main tracking means. Some deGoogled phone users uninstall PlayStore after then install their apps.
DeGoogled phones use apps from Fdroid, which are opensource. But for many commonly uses apps which are considered spyware but are used by everyone, people compromise and install them to varying degrees. They use Aurora Store to use apps from the Play store but logs in with a spoofed ID. Or users can download apps from other stores online and install them.
When not using GooglePlay services (which handle notifications for apps on the phones most people are familiar with), deGoogled phones use MicroG (a Google service emulator, simulates Google so apps think they're talking to Google, and it communicates with Google to get notifications but Google doesn't actually see the phone because MicroG is in the middle handling the interaction).
Paid apps don't work on deGoogled phones people say, because you need the PlayStore for that.
People say in the future security people will possibly just switch from phones to computers.