I donated to Replicant, but after reading the documentation felt a little overwhelmed and scared to try installing it on my phone. Although firmware blobs are "bad" and "not free", I was afraid I would probably brick my phone with no previous experience at this.
The wiki at the Cyanogenmod site looked a little better documented. Since they are probably the biggest alternative it also seemed more likely for me to be successful. So I decided to try them out for my attempt.
It was still quite an effort. The Android SDK doesn't run properly on my AMD64 Debian Wheezy by default - specifically the adb and fastboot tools. Fortunately Debian has packaged up adb and fastboot already. Although they aren't released for Wheezy, it was easy enough to download the package sources and compile them myself.
In order to run adb, I had to enable USB debugging mode on my phone. I may just be slow but it took me a while to figure out what that meant and then find this article. It turns out I needed to click the "build number" seven times to reveal the hidden developer menu and then find the right checkbox.
The next problem was that the recovery image kept getting overwritten after each boot. This caused quite some confusion as I stumbled through the steps and had to back up a couple times. I got proficient at reflashing and booting into the recovery image!
In the end, I am proud to say I was successful. I've installed an SSH server and even Midnight Commander on the phone, and have enjoyed ssh'ing in and poking around the file system. Maybe my next project will be Replicant.