(This was originally on my old website, I have resurrected it here.)
An outline of my Android setup. Hint: Mind the GApps.
I'm currently on CyanogenMod, but may go over to an AOSP ROM sometime.
I don't flash GApps, but if you want to, I recommend OpenGApps. However I do use Signal which needs play services for GCM, there used to be LibreSignal which could do the messaging component of Signal by using web sockets to connect directly to OWS's servers, but it is now dead. Thankfully microG lets us use GCM.
Almost all of my apps come from F-Droid, I can't praise F-Droid and all of the open source developers enough, F-Droid is a treasure trove of high quality useful apps.
This is device specific, check XDA for how to get TWRP onto your device. Download CyanogenMod, boot into recovery and flash it.
Also flash OpenGApps before the first boot if you want to.
Some of the apps I use need root, enable this under developer options (tap build number 7 times) in CyanogenMod. For other ROMs, use phh's SuperUser. Note: never use SuperSU, it is closed source and Chainfire sold it to CCMT.
Complete the initial setup and then install F-Droid.
Xposed is a framework for code injection, microG needs a module for signature spoofing, so it can pretend to be the official play services. Only use modules that you trust, they tend to be small so you can look over their code quickly.
Get Xposed here. Flash the framework zip in twrp, then install the materialised installer.
Install the FakeGApps module.
Add the microG repo to F-Droid.
See here for detailed instructions, the gist is to install the services core, gsf proxy, and fake store. Enable device check-in, and cloud messaging in microG settings. Finally reboot.
All of these apps are available from F-Droid:
Enable the Guardian Project repo to get:
Not on F-Droid:
Edit: I neglected to mention that the first time you install Signal it should come from a trusted source (e.g. copy it from someone who is happy to use the play store), then updating via APKMirror is safe, since the signatures will match.
Also Raccoon might be useful, a desktop play store client.