It depends on the CPU you currently have, but I would say, especially for the 6800's and the X800's, for you to get the fastest CPU your mobo (and budget) will support. Also, if I was you, I would stay away from the S478 Prescott's as they are not very good (Prescott in general is simply lackluster). Go with a Northwood P4, as it is, in my opinion, the best rev of the P4 Intel has produced.
On another note, I would also recommend that you update your BIOS before upgrading the CPU, as it can oftentimes improve performance and stability with machines.
Also, what is the mobo you are using (I.E. 875P, 865, PT800, etc)?