Alright, my parents' PC has become bogged down by mysterious forces, the nature of which I have no comprehension. I've given a fair bit of effort to sprucing it up, but I'm almost certain it's infected with a near-invisible piece of malware. Rather than spend the rest of the year trying to fix it, I'd like to install linux as a replacement.

I have moderate experience (mostly at school) with linux and do not fear the command line, but not so for my parents. As a CS guy, I've been extremely annoyed with KDE (openSUSE, as it were) before, and I think my parents would smash the monitor, so I'd prefer something that uses GNOME. Obviously, it needs to be fairly friendly and easy enough to figure out with experience only in Windows XP (that is, Windows user friendly).

"Ooh, ooh," I hear you say, "Ubuntu!" Well, there's my problem. I installed a recent version (using Wubuntu, if that makes a difference), and it runs slower than a cheap fan in molasses (seriously, I couldn't get Firefox to run and gave up after 20 minutes or so of waiting).
Thus, I need something significantly lighter than Ubuntu, no more intensive than Windows XP.

The box has:
256 MB RAM
Intel Celeron D 335 running wtih 2.8 GHz and 533 MHz FSB
...and that's about it.

A note on the user friendliness: I can (hopefully) handle anything that gets sticky, but it should be plenty simple to log in, open FF, and check some email.

I know this might be a tough order, but any recommendations would be tons of appreciated.

PS: If it could be parallel installed with XP, that'd be great (but I think you can do that with just about anything, right?).

Welcome to LQ

Take a look at
puppy, tiny core, debian with xfce ...
http://www.tinycorelinux.com/
http://www.debian.org/
http://www.puppylinux.com/download/index.html

you could also take a look at xubuntu if you tried ubuntu. Xubuntu will install on low spec machines.

Neither Gnome nor kde will run well with only 256mb of ram.

Your best bet would be something like lxde.

http://lxde.sourceforge.net/screenshots.html

Processes 102 Uptime 16:20 Memory 165.2/493.6MB That's with Firefox using chatzilla and 6 open tabs, lxterminal, pcmanfm, last.fm streaming using shell-fm, and my tux droid hooked up and running.

Also try antiX - it's designed for those older PCs.
( antix.mepis.org)

Also,
till you get comfortable
or just wanna check out different distro's
you could load a bunch on usb and boot 'em all persistent and
judge what you want without touching xp or hd

newest tinycore rocks and is lowram and remastersable
I'm remasering puppy, tinycore and pmagic off usb now
http://multidistro.com/shots/scrnshots.html

To go even lower RAM, you could do hd install of puppy to usb or hd
and it'll use less memory too

I would suggest PCLinuxOS LXDE
PCLXDE 2009.4 is a minimal self-booting/installable Linux Live CD that features the LXDE desktop environment along with a small suite of lightweight applications designed for use on low end computer systems. It is small, fast and fun. Designed for P III or better. Does not work on K6/2 processors.

I agree with the above. Try a distro that offers LXDE if you stay with that sort of memory.

However, I do have a AMD Athlon 1.2 GHz machine that runs KDE 3.5.10 comfortably (Gentoo distro). The difference is that that machine has 1GB memory. Your CPU seems ok, so if you can find some cheep memory to add to it, you might find your choice of Linux distros get much wider...

Mons