One of my desktops is a Gateway 300S with a Intel ESSEX2 motherboard. Im
running a 2.2GHz Celeron with 400mhz front bus. It (the specs) say I
could also be running a P4. I contacted Gateway and they said that while
they do not offer a upgrade CPU for this system, yes you can upgrade
yourself the cpu.

Even though I build Shuttles left and right, Im a bit at a loss on this
next part as I havent done this before.

This is from the docs:
"The motherboard has a 478-pin zero insertion force (ZIF) socket that
supports a single Intel® Pentium® 4 processor or a single Intel Celeron™
processor based on the Pentium 4 architecture. The standard host bus
speed of the motherboard is 100 megahertz (MHz). However, the processor
uses a dual-clock, un-pipelined processing method that achieves system
bus speeds up to 533 MHz."

I also discovered that my 1GB limit is actually 2GB.

So, what Im doing is upgrading the ram from 768 to 2gb and wanting to up
the CPU. Looking at Newegg I see quiet a few choices but, most of them
are 800MHz. If I get say a P4 3.0E Prescott 3GHz that is 800MHz even
though I have a 533MHz, will the CPU just run a bit slower or, would a
P4 2.8 Northwood running at 533MHz be a better choice?

Im really hoping to run Fiesty better with these improvements because at
the moment, this computer is running slower and slower.