Android is an astonishing commercial success, and is often touted as a Linux success. In some ways it is; Google was able to leverage Linux and free/open source software to get Android to market in record time, and to offer a feature set that quickly outstripped the old champion iOS.
But it's not Linux as we know it. Most Android devices are locked-down, and we can't freely download and install whatever operating systems we want like we can with our Linux PCs, or install whatever apps we want without jailbreaking our own devices that we own. We can't set up a business to sell Google Android devices without jumping through a lot of expensive hoops (see The hidden costs of building an Android device and Secret Ties in Google's "Open" Android.) We can't even respin Google Android however we want to and redistribute it, because Google requires bundling a set of Google apps.
So where do you go to find real open source Android? Does such a thing even exist? Why yes it does.
F-Droid: FOSS Repository
There are quite a few Android repositories other than the Google Play Store, such as Amazon Appstore for Android, Samsung Galaxy Apps, and the Opera Mobile Store. But there is only one, as far as I know, that stocks only free/open source apps, and that is F-Droid (figure 1).
F-Droid is a pure volunteer effort. It was founded in 2010 by Ciaran Gultnieks, and is now operated by F-Droid Limited, a non-profit organisation registered in England. F-Droid relies on donations and community support. The good F-Droid people perform security and privacy checks on submitted apps, though they wisely warn that there are no guarantees. F-Droid promises to respect your privacy and to not track you, your devices, or what you install. You don't need to register for an account to use the F-Droid client, which sends no identifying information to their servers other than its version number.
To get F-Droid, all you do is download and install the F-Droid client (the download button is on the front page of the site). Easy peasey. You can browse and search apps on the website and in the client.
Other FOSS Android Directories
DroidBreak is a nice resource for finding FOSS Android apps. DroidBreak is not a software repository, but a good organized place to find apps.
AOpenSource.com is another FOSS Android directory. It gives more information on most of the apps, and has some good Android books links.
PRISM Break lists alternatives to popular closed-source propietary apps, and is privacy- and security-oriented.
Now let's look at how to get a FOSS Android operating system.
CyanogenMod is one of the best and most popular FOSS Android variants. This is a complete replacement for Google's Android, just like you can replace Debian with Ubuntu or Linux Mint. (Or Mint with Debian. Or whatever.) It is based on the Android Open Source Project.
All CyanogenMod source code is freely available on their Github repository. CyanogenMod supports bales of features including CPU overclocking, controlling permissions on apps, soft buttons, full tethering with no backtalk, easier Wi-fi, BlueTooth, and GPS management, and absolutely no spyware. Which seems to be the #1 purpose of most of the apps in the Play Store. CyanogenMod is more like a real Linux: completely open and modifiable.
CyanogenMod has a bunch of nice user-friendly features: a blacklist for blocking annoying callers, a quick setting ribbon for starting your favorite apps with one swipe, user-themeable, a customizable status bar, profiles for multiple users or multiple workflows, a customizable lockscreen...in short, a completely user-customizable interface. You get a superuser and unprivileged users, all just like your favorite Linux desktop.
CyanogenMod has been ported to a lot of devices, so chances are your phone or tablet is already supported. Amazon Kindle Fire, ASUS, Google Nexus, HTC, LG, Motorola, Samsung, Sony, and lots more. A large and active community supports CyanogenMod, and the Wiki contains bales of good documentation, including help for wannabe developers.
So how do you install CyanogenMod? Isn't that the scary part, where a mistake bricks your device? That is a real risk. So start with nothing-to-lose practice gadgets: look for some older used tablets and smartphones for cheap and practice on them. Don't risk your shiny new stuff until you've gained experience. Anyway, installation is not all that scary as the good CyanogenMod people have built a super-nice reliable installer that does not require that you be a mighty guru. You don't need to root your phone because the installer does that for you. After installation the updater takes care of keeping your installation current.
Replicant gets my vote for best name. Please treat yourself to a viewing of the movie "Blade Runner" if you don't get the reference. Even with a Free Android operating system, phones and tablets still use a lot of proprietary blobs, and one of the goals of Replicant is to replace these with Free software. Replicant was originally based on the Android Open Source Project, and then migrated to CyanogenMod to take advantage of their extensive device support. Replicant is a little more work to install, so you'll acquire a deeper knowledge of how to get software on devices that don't want you to. Replicant is sponsored by the Free Software Foundation.
The Google Play Store has over a million apps. This sounds impressive, but many of them are junk, most of them are devoted to data-mining you for all you're worth, and how many Mine Sweeper and Mahjongg ripoffs do you need? Android is destined to be a streamlined general-purpose operating system for a multitude of portable low-power devices (coming to a refrigerator near you! Why? Because!), and this is a great time to get acquainted with it on a deeper level.