It could actually be that you have so much hardware it's slowing things down! I have an AMD Athalon 2500 at 1800MHz, 512M RAM, and a 7200RPM ATA drive. Firefox loads in 2-3 seconds, ooffice in ~8. Not sure of my boot time, not going to reboot now just to check.
You might looking into doing some sort of suspend-to-disk if you want faster startups, but changing distros will probably give you the best speed-up for the least cost and effort. Fedora is not a high-performance platform, it's a robust, easy-for-users, works-with-almost-anything approach that includes several different types of kitchen sink.
Mandriva was originally forked off of RedHat to provide a speed-optimized version of the distro, and that's what I'm running here. Being RH derived, you'll find it very familiar. Gnome is available, although KDE is the default. Many third-party programs are available, version upgrades work pretty well, and applications are frequently back-ported to existing releases. Any GUI based package manager is going to be a system hog, but the console based urpmi package management system is excellent (you MUST get good mirrors though).
Ubuntu is the obvious choice. "Everybody's" using it, and they are working on an optimized parallel boot system.
One choice that might help - try installing lilo instead of grub. I think it's faster, but I like it better anyway.
As always, your mileage will probably vary.