I found that most of my stability problems were solved when I went to a better hs/f.
You can do a lot of good with case fans also. The advantage to case fans is that they continuously change the air in your case. Air absorbs heat faster when the there's a big diffference between the heatsink temperature and the temperature of air in the case. In a (bad, closed) case with few fans or vents the air will eventually heat up to the temperature of the heatsink and do nothing no matter how fast the air moves.
If you mostly surf the web then the OEM heatsink alone is fine, but if you play games for hours on end, you'll run more dependably with extra fans and/or a better heatsink.
Your new fan will plug directly into the motherboard, yep.