The problem
Stock Android is very bad for privacy. Google Android runs Google play services which collects everything all the time. It also provides APIs that apps use to target users and gather data. What is worse is that almost all of the AOSP apps provided by AOSP have been replaced with proprietary Google ones. Everything from the messaging app to the clock app is collecting data. In Google Android you are expected to use Google apps and I don’t think you can install Play store apps without signing in.
What I use
I use Lineage OS on phone it works for what I need. All of my external apps are from F-droid and I don’t use any proprietary apps what so ever. The stock apps are very good so I don’t need things like a third party Camera app. I have also have done some simple hardening such as setting the private DNS setting which turns on DNS over TLS. I use a bunch of different F-droid apps I use but one of the more important ones I use is Organic maps.
While this setup is mostly solid it does have some serious draw backs. Because I don’t run MicroG or Play services I can’t use any traditional apps. Also Lineage OS does not support boot loader relocking which means I am vulnerable to evil maid attacks.
Other options
When I first started to move to private alternatives I initially used Lineage OS with MicroG. MicroG is a bit like Google play services but it is Foss and designed to be much more private. It spoofs the Google signature and provides many of the APIs found in stock Android. The biggest limitation with MicroG is that it doesn’t fool any Google software. To use anything like Gmail or Gmaps you need to have Google play services.
If I were to do this all again I probably would start with Calyx OS. The Calyx OS team seems to be made up of good people and they ship a Android experience that is privacy friendly. It comes with MicroG installed and setup and the bootloader gets relocked during install. The downside with Calyx is that it has less supported devices. (Although they are trying to add more) It is also farther behind in the update process and the apps are not as polished as in Lineage OS.
One of the things I see frequently is people recommending Graphene OS. I personally do not support Graphene OS and I wouldn’t recommend that you use it. It is better than Stock Android but that is about it. If you want more details let me know but I am trying to keep this short and sweet.
Note on Android security
One of the things I keep hearing Wendel mention is that he wishes Android had sandboxing. I am not quite sure what he is talking about since Android as some of the best sandboxing of any platform. The android security model follows least privilege and each app runs in there own isolated environment. The actual sandboxing is done with SELinux and it very strong. There have been very few exploits over the years and there is only one piece of malware that I know of that managed to persist across a factory reset.
The real weakness in Android is the proprietary kernel baggage. The Android device kernels are based on specific Linux kernel versions and you can’t easily mainline a device. Almost all of the hardware is dependent on proprietary blobs that can not be replaced. If there is a publicly disclosed vulnerability you better hope that Qualcomm is feeling nice as if they don’t patch it you are out of luck.
Update:
Why I don’t like Graphene OS: A very brief intro into Private Android - #13 by Darin755