You'll need to stick with a CPU using the LGA775 socket. I believe that the Core 2 Duo/Quad and Pentium E (these are basically Core 2's with a slower FSB and less cache, the other Pentium's and such are older technology) should work just fine.
A service pack is a collection of fixes that Microsoft has rolled into one package. Each Service Pack is cumulative, so you only need to install the latest one, not each individual one. Depending on the fixes, you may see a speed improvement.