More memory will likely help but normally it is the rubbish that Windows collects when you un-install it never removes it all. Re-installing windows to a different location to original will normally cure it without losing docs etc. But every program will need reinstalling. And so PC's don't have install disks that allow that and its all or nothing. Also some PC's have windows hidden in a partition so formating can get rid of your copy. There are clean up programs which work to an extent. Remember to back-up all important files. I have in the past thought I was formating a partition and by mistake done the whole drive. Also you can go into control panel add and remove programs and remove ones you do not use. And look in Start/All Programs/Startup and drag any ones you don't use much out of that into another place on all programs. But be safe back-up any files you don't want to lose.
When starting up, more memory possibly won't help much as if you have so many programs to load, then the bottleneck will be the hard disk not being quick enough to load everything. Hard disk speed hasn't increased much in the last few years so don't bother upgrading it. In some cases this can cause the CPU to hit 100% utilisation (or so the Vista Sidebar gadget says on my machine - an AMD 64 dual-core machine) but RAM utilisation is roughly 50-60% (with 2GB - Vistas recommended minimum size. XP's recommended minimum is 500MB).
A lot of applications also install small 'quick start' programs that load on Windows boot-up just in case you run the full applications it will load quicker (Real Player and Adobe Acrobat Reader are just 2 examples). In many cases these days if you stop the 'quick-start' program from loading the full application will only take slightly longer to load.
To stop them running in XP and earlier type 'msconfig' in the run command (on Vista it's in the 'Start Search' box). When open, click on the startup tab. All the programs that run on start up will be listed here, not just the ones in the startup folder on the Start Menu. To disable them untick the box next to the item. Be VERY careful not to untick the programs Windows needs to load!! If you know what the program is (looking at it's location path is normally a big clue) and know you don't want to open it at start-up then untick it. Click OK to close MSConfig.
The biggest program to slow the machine down on boot-up is your anti-virus software, and I wouldn't advise you to turn that off!
Start with a freeware programme called CCleaner. Use your internet search engine to find it. That will get rid of a vast amount of junk some of which you will never even know that it's there. Run it regularly.
How much free space does your harddisk actually have. If it's seriously full then the dynamic windows memory (filename pagefile.sys) will have problems running properly and will slow the machine down. You really need to have at least 20% freespace available.
When was the last time you defragmented your hard drive? If it's fragmented then there is a windows utility to do this although I prefer to use Diskeeper.
Just removing files won't necessarily help if the registry is so large, fragmented and generally bunged up that it ties up an enormous amount of system resources just keeping up. Get a programme like Tune-Up Utilities which will sort this and a whole raft of other stuff as well.
Basically what I'm saying is that it sounds like your system could do with some maintenance.
I'd be careful with CCleaner, it can delete some important files needed for running windows. It's happened to me on a couple of occassions. Generally it is ok.
I'd advise checking for viruses first to ensure that isn't the issue followed by a spyware scan.
Also if you have lots of little icons next to the windows clock they are likely to be using up vital cache so will slow your pc at startup (Which is the symptoms you described) so untick their options that say run at startup. If you are advanced you can look at/remove startup items in the Windows startup folder and also do a Start>Run>msconfig and untick any old uninstalled programs from the startup. This normally helps me.
I've only had 2 PCs in about 10 years as I follow this routine on a regular basis, along with regular defragmenting of the drive afterwards. (A forgotten tool!!)