Hello newbie, that's easy to answer.
Get yourself a Duron and an overclocking board like the Asus A7V or the Abit KT7. Cheap Durons start from 650MHz and they overclock plenty. You won't need to buy new memory, though at today's prices another 128Mb would be a very good investment.
You can get what you want for waaaaay less than $500!
Happy hunting.
*By the way, I would look at your hardrive also if it is more than a year old. Durons are 95% as fast as Athlons and both p1ss on Celerons from a great height.