I'm definately getting Firefox for them. They've never used AOL, which is a very good thing. Scytale, your idea sounds like a lot of fun to play with, but I don't know enough about computers to do it, and don't really feel like learning.
The big problem is that they are easily suckered by flashy things; game downloads (my mom was OBSESSED with Mah Jong for a while) and screensavers and the like. When I was living with them, I had it set up so that their user accounts didn't have administrator rights, and they had to ask me to download stuff for them. Once I moved out, they whined around and made me set them up as admins, so now they can download anything.
I'm going to lobotomize their hard drive, and use the destructive-recovery option to return it back to normal. That should keep it clean for a while.