For each of the "styles" I used multiple, overlapping layers. The effect is based mostly on guitar amp simulators, namely Guitar Rig and Amplitube (both have "free" versions for you to use). The entire thing is squashed by using loads and loads of compression. Additionally, down-tuning a layer or two by 1-3 semitones seemed to enhance it dramatically. Cutting some low end and a bit of high end makes it more audible. Then it's just a matter of clearing it up with surgical EQ and sculpting it a little. Bit Crushers and additional tube saturation can also come in handy.
I can dig up the archives for the specific effect chains and processes I used if you are really interested.
For computer voice, aside from the mentioned vocoder, I would also advise using a heavy ring modulator and mix it with "raw" material. A very nice effect can be achieved by using pitch correction software like Melodyne with dramatic quantization and pitch change settings. I'm not sure if there are any free alternatives or built-in tools for Audacity to achieve this though.
A few useful free plug-ins:
Many thanks for all the detailed advice ... absolutely exactly what I was after so very much appreciated. I'll start experimenting based on your advice and see what comes out of the process!