A possible solution is to use only free software on your phone; unfortunately both Ubuntu Touch and Firefox OS are too premature for my needs, so I have to use CyanogenMod and avoid to use intrusive app. Let me explain you what I did, and please should considere to use more free software app as possible.
I choose to use CyanogenMod as system because is probabily most famous Android Rom, with a great support and always update. For my Samsung Galaxy S4 there is version 11 yet, with Android 4.4.2. Unfortunately there are some blob, that are proprietary driver, but the rest is almost completely free software.
After I flashed the device (there is a guide on official wiki, if you are interesting) I didn’t flashed Google Apps, to have not proprietary service from Google on the phone. The first thing we need is a store, without PlayStore we can’t install app! Obviusly, there is a solution: it’s called F-Droid, is a market with only Free Software: you can download it from its site, and then use it like Play Store. It isn’t so cool as official store, but freedom has a price ;-)
First app I install is the browser: I choose Firefox, it’s open- source and have sync with desktop, where I use Firefox too. As well as for browsing the web I use it as a subsitute for Facebook, Google Plus and Twitter, because I don’t know an open-source client for social networks. The disadvantage is that you do not have push notifications but, hey, this significantly increases the productivity! Social networks aren’t my work, so if I check updates once an hour isn’t a drama.
Second most important app for me it’s mail client: instead of the app by default I use K-9 Mail, a very powerful app with support for GPG. Awesome! To replace Google Maps I suggest OsmAnd~, a client for OpenStreetMap, a project like Wikipedia, but for maps. If you need to sync your calendar and your contacts with a server that supports DAV the solution is DAVdroid: I use it to sync contact and appointments with my istance of ownCloud, and I use official client for Android to access to my files on my server.
As music player I think the best choice is Apollo, that is default on Cyanogenmod, to search on web I use, like on desktop, DuckDuckGo, a search engine that respect your privacy. For RSS reader I choose [TTRSS- Reader][rss], because I have a istance of Tiny Tiny Rss on my server. For two step authentication I use a old version of Google Authenticator, when it was still free , but I’m working to have FreeOTP on F-Droid: FreeOTP is a free authenticator developed by Red Hat.
Other apps that I think are interesting are AdAway, to block intruisive advertisements, UberSync, to sync your FB contacts with your address book, and Wikipedia, because knowledge is power. You can find others substitutes on Prism Break.
Only closed app I use is Whatsapp, but I want to delete it soon. You can download it from official website, without Play Store.
I hope that these alternatives may be useful to someone :-) And you, which free apps use?