Wherever possible, I prefer to use open-source software. I do just about everything on my laptop in Firefox or a Linux shell with tools like Vim, Git, SSH, etc, so that's pretty much a wrap, but proprietary software is everywhere on Android, my phone has ended up with a lot of it, and I'm making a conscious effort to fix that. So far, I've replaced most of my most-used applications.
It's worth noting that a lot of Android is already open-source. I've installed CyanogenMod, which is based on the Android Open Source Project, and without having to add any closed applications, I can read IMAP mail (though the AOSP client still doesn't support IMAP IDLE). CM also gives you root access by default, which opens up more options for things like backing up data. I use Google Authenticator, which is open source and implements OATH, which is an open standard for one-time passwords. This gets me into many services that really need more than just a username and password protecting them, and it's great and easy to use. Google has also released Google Sky Map as an open-source application, and I enjoy using it for some on-the-spot amateur astronomy.
One of the best resources I've found for finding additional Free Software for Android is F-Droid. They have a list of software, all of which is released under some Free license, and you can browse either via the web, or their Android app. The App can also function as an "app store," of sorts, though there's no payment method, since everything is free.
Instead of Google Reader, I have TT-RSS installed and running on Red Hat's Openshift using Amit Shah's instructions as a guide. I may pack this into a Quickstart for easier deployment, plus his instructions throw a few things in the persistent data directory that I don't think need to be there, and I still had to load the MySQL schema manually (I assume he used PHPMyAdmin, and just didn't mention it in his article). This replaces both the Google Reader web app and mobile app - there's an official TT-RSS client on the Play Store or on F-Droid, though that client requires a $2 payment after 7 days use. Since it's open-source, you could hack the source, cut out the timeout, and rebundle the APK; it's probably pretty easy, and if you don't want to add your credit card to Google Wallet, probably your only recourse. However, I just paid for the app; I'm happy to support a developer who's been dedicated to a great project for years (even if I still miss Gregarius). It's also well worth noting that TT-RSS does some things Google Reader doesn't - it's social features aren't tied to Google+, so you can share via Owncloud, Identi.ca and lots of other services. TT-RSS also lets you filter out items from feeds (I automatically throw away all of Peter Bright's articles on Arstechnica, for example), and, in my experience, TT-RSS does a better job filtering duplicate items from feeds than does Google Reader. Another bonus, the desktop client Liferea does a much better job integrating with the TT-RSS API than with Google Reader.
There are a few open source apps I've depended on for as long as I've had a mobile device. FBReader is my app of choice when it comes to reading ebooks, and I've been using it since I had a Sharp Zaurus, through the Nokia 770 and N810, and now a couple Android devices. F-Droid shows that there's also Cool Reader, but I'm so satisfied with FBReader, I don't see myself changing.
ConnectBot is a good SSH client, though I find myself using the likewise free Terminal IDE (not on F-Droid, though I think it should be), which gives you several TMux shells, for most shell and SSH operations.
I use Firefox over the Android Browser or the new Android version of Chrome. It's still pretty sluggish, but I've come to rely heavily on Firefox Sync to keep my browser history, bookmarks, saved passwords, and other personal data a) synced across devices and b) out of the hands of marketers and busybodies.
I have OwnCloud running on Openshift, which acts as a data store and syncing service, as well as Piwik, which tracks web activity on my websites, and both have open-source Android clients. It costs $1 to install Owncloud from the Play Store, but not from F-Droid.
It's worth noting that the Github Android client is Free, even if the web service it talks to isn't.
Let me not forget games. There are tons of games on the Play Store, most of them proprietary, and lots of them rely on spam (banner ads, or worse) to generate revenue. I like a lot of them, and will probably hang onto some. But, there are some interesting games on F-Droid. Andor's Trail is a very nice roguelike game, as is Meritous. Frozen Bubble, which my wife was obsessed with for the better part of a year, is open-source. The classic GLTron is ported to Android, as is Tux Racer. There are emulators for the Game Boy, NES, N64 and PSP, as well as the open-source distributions of Doom, Quake and Quake II, and some Tetris clones. Taps of Fireis a Guitar Hero-style game, which is fun. There are also numerous simple puzzle games, card games and board games on F-Droid. Battle for Wesnoth is not on F-Droid, but it is a port of the excellent open-source strategy game of the same name. So, if you really want to cut proprietary software out of your phone, you don't need to give up gaming entirely. I do plan to hang onto Minecraft and Swords and Sorcery, though.
My current efforts to switch applications are around podcasting and note taking. I'm using Pocket Casts for podcasting now, and it's non-free, relies on a non-free central host for downloads (ostensibly to speed up transfers, but probably more for tracking and monetization), and has a rather ostentatious UI. I have AntennaPod installed from F-Droid, and it seems promising, with a nice UI that conforms to the Android 4 HIG, and claims to support OGG, though I don't have any OGG-format podcasts to test it with.
For note-taking and tracking tasks, I've been using GTasks, which syncs to GMail. I'm currently trying to teach myself Org-Mode (though it'll likely be Vim Org-Mode, because I already have over a decade invested in Vim), and so I'm messing with MobileOrg. This is what some refer to as "fighter jet" software - there's a million dials and switches, and it's intimidating at first glance, but learning to use it well pays off huge in the long term. There's also Astrid, which isn't on F-Droid, but is on github. The version on the Play store has added integration with lots of weird proprietary services I don't want to deal with, so I don't think it's for me, but it is more user-friendly than MobileOrg, so it may be worth evaluating.
Obviously, I need to switch off GMail. I just migrated mail hosting for this domain to GMail off my old Linode (since 2003! sniff) a few months ago, but I'm considering moving my mail again to Lavabit, or some other mail hosting setup, as long as they also support XMPP. That would mean going back to an XMPP client (of which there are several on F-Droid), instead of the GTalk service, which, in my experience, all work fairly poorly compared to GTalk.
I haven't evaluated the various OpenStreetMap applications as an alternative to Google Maps; with the amount I rely on Maps, I doubt I'd switch, but it's definitely something to try. I also rely on Transit Tracks to find my bus arrival times, and MyFitnessPal to track calories- neither of those have replacements in F-Droid. On the other hand, I've already written a very simple client for the CTA API, so writing a new open-source app might not be hard (though I can't distribute the API key on F-Droid, so users would have to get their own). It's important to have a fairly complete database of foods in order to make calorie counting easy, so I'm not sure how hard it'd be to write a new calorie counter, but I bet a lot of their data comes from free (lower-case f) sources, so it's not completely impossible.
My quest is still far from complete, but I'm moving along nicely, and I hope this list of references pushes some folks to switch to open-source Android applications.