But when it gets hot, the fan is instructed the max out. And then you feel the heat being pumped out. I can see what many would think it's the fan that makes it hot.

To help on this issue look at CPU speed control programs to drop the clock rate. Since you run Linux here's a google of content for you -> http://www.google.com/search?hl=en&q=LINUX+SPEEDSTEP&btnG=Google+Search&aq=f&oq=

In closing, be sure to blast the heatsinks and vents with some canned air.