A new motherboard (your 1999 motherboard is not capable of any sensible upgrade).
From that follows a whole choice of bits to stick on. First thing I recommend having been through both processor type is to dump AMD and go Intel.
You then have the choice of dual core or quad core. I suspect you'll go for dual core on a cost effectiveness basis (Core 2 Duo to be precise).
Then there's processor speed. To be somewhat future proof (you can't be, of course), get the highest speed CPU you an afford and choose the motherboard accordingly. I have chosen an nForce motherboard for my recent upgrade; they have the advantage of being nVidia graphics friendly.
I'm wanting to build a new computer but I'm having trouble, it's been a long time since I've built one and my head is starting to spin just looking at ...