Thanks for the replies.
Bottom line is I have to do this upgrade without my wife finding out -
So, yeah it needs to be tight :P
The prices I was finding on the X800 XL were for the PCI-E
... the AGP is substantially more. In any case, I'll go ahead with the CPU for time being, and get a video card when I find a good deal.
Ram situation isn't bad - I have 768 MB at the moment. I suppose I should swap out the 256 for a 512 at minimum.