Look in the bios, you should find a setting for your cpu fan speed (it is usually called Smart Fan). If it is set at anything other than Manual - 100%, then your fan speed may wavier up and down.
As for a new heatsink and fan, in what Country do you live (so we can provide you with valid shopping links). And what kind of a budget can you afford? Will you be overclocking? And yes, you'll need to replace the thermal paste but it's very easy to do.
Thanks alot I will probably get the second one due to the quality... I notice that its sideways..is the installation the same? Also, I cant see the cables on those pics but I hope it doesnt have the same thing that mine has right now Will I be able to overclock a little bit with that one?This is as close to a stock heatsink that I see and it's $30 plus shipping.
Dynatron G785 2U Server PWM CPU Cooler - Intel® Nehalem LGA 1366 - FrozenCPU.com
I would spend the extra $10 and get this instead, it's a far superior heatsink.
Thermalright CoGage True Spirit 4-Heatpipe Core i7 CPU Cooler (Socket LGA 1156** / LGA 1366) - FrozenCPU.com
And yes, clean the old paste off with rubbing alcohol and reapply new paste. Only use as much paste as a single piece of rice.
WOW! That really is huge! No wander...just as an FYI the heatsink Slaymate uses is this
Thermalright "Limited Edition" TRUE Copper Ultra-120 eXtreme CPU Heatsink (Socket LGA 775/LGA 1366/LGA 1156*/AM2/Xeon*) - FrozenCPU.com