I'd encourage backing up, reformatting, and reinstalling the OS. I do it once a year on all of my machines at home and it's like getting a whole new computer. Installing, updating, and configuring everything can take a day to do, but it's well worth it.
RAM, yes. Watch for deals out there. Sometimes there are some nice fluctuations when a new RAM type comes out where your RAM will drop in price - sometimes very temporarily. I was able to get 512 chips PC133 for $20 a few years ago just before they jumped up to the $80 range again the next week. They're down around $50 now I believe (haven't needed to look lately).
You can never have too much RAM. I have one old machine that only has 512 on it (400 MHz), but the rest all have 1.5 Gig. They never put enough RAM on computers when they sell them. It's always an extra upgrade/hidden cost/gotcha.
Added: I checked - PC133 SDRAM that I use in a few of my PCs are going for $89.99. Thank god I loaded up when they were $20.
PC2100 512MB 266 MHz DDR goes for around $50 right now, but you can shop around. Maybe someone has some good sites they can post to watch prices.