My Barton 2500+ (OC to 2.14 GHz) runs ~39 idle and I haven't seen it over ~42 under full load for hours. My case stays ~27-28 usually. I have a Tt Volcano 7+ on the middle setting. I think you can get one for around $25 shipped.
EDIT: If you want cheap, just stick with the stock HSF. Monitor your temps and if it runs too hot for your liking then upgrade. The new HSF have much thinner fins than old XP's.