It's not exceedingly hard, as long as you have knowledge of how to open up the computer's chassis, removing the old motherboard and bolting in the new one. For a P4, an ASUS P4S533 (based on the SiS 645DX chipset), is extremely cheap, stable and performs pretty well. A P4 2.0 GHz will do for this situation. As for the videocard, I recommend having a GeForce3 Ti 200 at minimum (seeing as they are less than $100 now), but if you can spend the extra, a GeForce4 Ti 4200 is recommended. As for sound, if you can't live with integrated audio, a Creative SBLive! Value will do.
I also strongly recommend upgrading to a larger capacity HDD along with a DVD-ROM drive.
Prices: (according to Pricewatch)
ASUS P4S533 - $105
P4 2.0 GHz CPU - $178
GeForce3 Ti 200 64 MB - $82
Creative SBLive! - $20
If the cost of a P4 is too high for you, I suggest going AMD instead:
ASUS A7V333 - $101
AMD Athlon XP 2000+ 1.67 GHz - $120