For a while now I've been think how to regain control of my digital life. The first big just was switching to Linux about a year ago, just a quick install reintroduced me to the excitement I used to feel using my computer. Slowly after that I switched to more ethical services and open source software from my day to day, and it was amazing to see how just much more relaxing it felt knowing that I wasn't the product of a big corporation anymore. Then I decided to address the big, green, always listening elephant in room. My Android phone.
The quickest answer to this problem, as /r/privacy sometimes but mostly Apple says, is to buy an iPhone. That's most likely not the answer you're looking for, and frankly it's a bad one. The obvious answer to us Linux enthusiasts is to buy the Librem 5 phone when it comes out, and it'll be the best solution when it does launch but isn't a fix for the many Android user right now. Furthermore it may not be a solution to those unable to afford the Librem 5. The best solution I've recently tried is installing a custom rom and removing all of Google's software, so for those curious (@gyro), I just want to go over a bit of surface level of roms and my experiences so you can have a better idea of what to expect going this route. I will not be going over methods of how to install roms or rooting since it will be different for your specific device.
Google's Android V.S. AOSP
A bit of context that'll help explain the limitations of a de-Google life on Android. Google started Android as an open source project, as it still does to this day, however has managed to methodically implement proprietary control over the entire ecosystem. Ars Technica has a fantastic, if dated, article that explains this all in better detail which I recommend a quick read, but I'll give a quick summery. Originally all of Android's stock apps such as the gallery, music, and phone app were part of the open source project but as a fragmented Android market share began to swell Google deprecated as many AOSP apps to proprietary Google Play apps. On the developer side Google introduced proprietary APIs that made it easier to develop apps for Android, while making those apps reliant to the Google Play Services. At this point much of Android as we know it is tied to Play Services meaning when you switch to a custom rom which doesn't include GPS by default (that's a whole other story) the user then has a choice to make. Install the GPS via OpenGapps there by reintroducing the privacy issues before, live without GPS and see if they can survive almost solely on FOSS apps, or try something in the middle with MicroG, as the developers explain, "a free software clone of Google’s proprietary core libraries and applications."
Google's Android V.S. The Alternatives
So with that long winded primer out of the way, we need to quickly look at what options you have at your disposal. Roms are kind of like Linux distros in a way, all with various team sizes and whether or not they are based off another rom or its own thing entirely. Unlike Linux distros there are official and unofficial roms, the latter being typically ports of roms to phones with less development or long ended Android support. The biggest rom out there, and the easiest to recommend considering it's available for so many devices, is LineageOS which has its roots back in the days of CyanogenMod (again, whole other story). LineageOS however has a "less is more" philosophy keeping things as close to stock AOSP while adding just a few quality of life features, most notably Privacy Guard. For users looking for more customization, I'd recommend OmniRom as a good alternative. You may find roms with far more customization options like Havoc or Resurrection, but that can quickly be overwhelming and from what I gathered Omni is widely known as putting stability first. If you want a security focused rom, GrapheneOS is available for Pixel phones. If you're going to pick a custom rom you need to ask yourself a few questions:
How comfortable do I feel modifying my phone?
How much time do I want to spend maintaining my phone?
Am I willing to sacrifice stability and a bigger development community over more feature rich but smaller projects?
This is why I recommend LineageOS over most anything else because it's the best thing to a "it just works," solution. I encourage you to explore the XDA Forums for further research and to see what options you have for your own device. Keep in mind that the level of development support is different by brand and device so you may have less options than others. I would always encourage you to use official roms, however if your phone has stopped receiving updates long ago, your only option may be to run an unofficial rom.
Gapps, F-Droid, and MicroG
At this point you're probably tired of reading so I'm going to try my best to keep this short. Like I said, once you flash your rom you're going to be faced with a choice as to how you live your Android life. If you decide you want/need Google Play Services, you just need to flash the zip and you'll go about your day with very little change. All apps will work like normal, including Google tracking your phone, but you won't need to worry about reflashing Gapps again. I see a bit of confusion when it comes to OpenGapps thinking that this is a more secure alternative. OpenGapps is not an alternative, it's just the Gapps. You will have the option to only make the Play Store a system app, having more control over Google's other apps, but as long as Google Play Services is running on your phone, you are still at the mercy of Google.
The real alternative is F-Droid, an app store dedicated solely to FOSS apps. Thankfully with the flexibility of Android, this app store can be installed on any Android phone, no hacking required. I recommend doing this in tandem with going through the Privacy Tools website to find privacy respecting alternatives to all of Google's services. That'll make the switch to a custom rom without Gapps much easier. You do have to keep in mind Google's APIs I talked about earlier. This means that some FOSS apps will have some slight limitations, typically a persistent notification to keep the app in the background, and if you decide to use something like the Aurora Store to get apps from the Play Store you will have issues with those apps relying on Google Play Services for some functionality. If you paid for any in-app purchases you'll lose the ability to authenticate your purchase locking you out of pro versions of apps.
Finally the Goldilocks solution of MicroG. This project tries to re-implement GPS to allow for apps to function normally, to some degree of success. I've seen one post claiming that Cast support has been added to MicroG but I can't get it to work, and you can kiss Android Auto goodbye. MicroG provides a compatibility chart to help you get a sense of what works, but it's really a trial by fire as I've experienced. In order for MicroG to work, you will need a rom that supports Signature Spoofing, but if yours doesn't you can flash a patcher. One of the easier ways I've found is a project called Nanodroid which provides you some additional options like restoring your in-app purchases. You can either follow the instructions from MicroG or try flashing the Nanodroid zips. If all of that is a bit much, don't worry because there is a simple way to get MicroG. MicroG provides a fork of LineageOS, as the Lineage team has refused to add signature spoofing, so you can simply follow the LOS install instructions via their website for you phone using MicroG's rom.
Final Remarks: My Personal Solution
Last bit I swear, thanks for getting this far. I recently made the switch to LineageOS with MicroG (with a custom kernel but that's again a whole other story) and I already can tell it's an adjustment. I have an OnePlus 6 that I adore but I needed to tweak some things to get the battery performance and usability that I was looking for. My main worry was living without Android Auto and GMaps but the alternative I've found being Drivemode and HereWeGo Maps (both sadly proprietary and probably not privacy friendly but hey they're not Google) work well enough to get me most places. I needed to installed the Google app to get speech to text working but limit it heavily and without GPS or a Google account it can't do much. Everything else is business as usual for me since I've been preparing for this transition for half a year by weening myself off Google services.
Hopefully this will point you in the right direction of how to handle you Android phone, and if after all of this you just want to break down and buy the Librem 5 when it comes out, I don't blame you. I will be in the comments below answering some questions and updating people on my transition has gone for anyone interested. Perhaps this can also help @gbryant if he decides to do a video on the subject.