You will notice a big difference, unless you only use your computer to surf AOL at 28.8k. I upgraded from an Athlon Classic at 900MHz to an XP1600+. I hung on to my PC133 as well. Total upgrade cost - less than $180, including shipping and hsf. Anyway, your cost will be far less than mine, even if you do get a new hsf.
I recommend getting the XP1600+ from newegg and unlocking it. I've gotten a 300MHz overclock from my chip with poor cooling, so don't blow $40 on a new hsf if you are happy with your current unit. Fun little project, and the 51 extra SSE instructions and 500-600 extra MHz will really make for a nice upgrade.
jaybee