For a system to be secure one needs to be able to inspect it, so make sure you're using a Free Android system.
This pages complements that with information about apps that are not necessarily replacements for proprietary components of Android and the Google Apps, but which can improve your security and/or privacy while using various services.
SecDroid claims to disable various under-the-hood services that can have a negative impact on security.
Wi-Fi Privacy Police prevents the sending of some identifying information when scanning for Wi-Fi access points, and optionally lets you disable Wi-Fi entirely when not in areas supposed to be covered by your allowed access points in the first place.
NetGuard and AFWall+ are firewalls that can stop some of your applications from connecting to the internet (either on Wi-Fi or mobile data). The former uses Android's VPN hooks and as such it doesn't need root (but forces a "key" icon to show up on your status bar), while the latter does need root to change iptables(wp).
AdAway's main purpose is to stops advertisement, but since it blocks ad-related hosts at a system level, it can prevent a considerable amount of tracking. It does require root to achieve this, while a root-free alternative that uses the same method as NetGuard is DNS66.
WebApps can be used to make sandboxes for particular sites so that they cannot communicate with each other.
Both Conversations and Xabber support OTR(wp) encryption natively. Conversations can, in addition, make use of OpenKeychain for OpenPGP(wp) encryption. These programs can also be set to connect through Tor(wp) after installing Orbot.
The above programs support only XMPP(wp), while a supposedly secure, decentralized alternative is Antox, which utilized the Tox(wp) protocol. It can be installed through F-Droid but only by adding their own repository at https://antox.me/fdroid/repo. Aother distributed system is Ring, which works similarly to Tox(wp): it is at a less advanced stage of development at the moment, but it is less taxing on phone battery and network bandwidth.
You can use SMSSecure (now called Silence) to send encrypted SMS to other people also using the program.
If you prefer to avoid Twitter entirely, AndStatus also supports a number of Twitter-like networks. A distributed Twitter-like system is Twister(wp), although the Twister app for Android looks a little dated and looks like it needs a local server.
MaterialFBook is probably the best free Facebook client, as it doesn't simply wrap the website into an app, but uses the API to provide a more mobile-friendly interface, as well as, optionally, notifications and ad-blocking.
Facebook lite ("Face Slim") and Tinfoil for Facebook can be used as lightweight clients that wrap around the Facebook mobile site. They don't receive notifications, but Facebook Notifications can be installed separately to get them.
Many, if not most, smartwatch and fitness band "companion" apps phone home a lot, to let other people know how fast you run and such things... to grasp where this can lead, consider there is already a device touted as a wearable polygraph ("lie detector").
There are two main project to use smartwatches in a freer way: Gadgetbridge directly communicates with Pebbles(wp) watches, Mi Bands(wp), HPlus-based devices, the Amazfit Bip and potentially other wearables using a minimum of permissions. For some smartwatches that come with Android Wear(wp), that can be replaced with AsteroidOS, which communicates with smartphones using the free AsteroidOS Sync app. MicroG also contains preliminary support for Android Wear, but it is not in a usable state as of yet.