Yep, clean the old thermal paste off with isopropyl (rubbing) alcohol.
Regarding the aftermarket coolers: the top air cooler is the Noctua D-14 http://www.newegg.com/Product/Product.aspx?Item=N82E16835608018.
I don't know how the CM coolers rate against the Noctua.
The Corsair H100 seems to be the top rated cooler by Tom's http://www.tomshardware.com/reviews/h2o-h80-h100-benchmark-overclocking,3084-9.html,
but the Antec 920 received the top rank from Real World Labs http://www.rwlabs.com/article.php?cat=articles&id=442&pagenumber=8.
I prefer a closed loop cooler because it exhausts heat directly outside the case, and it provides better circulation. I modded the Antec 620 in my rig to a dual 120 mm fan in push/pull configuration and get results approaching the Antec 920.
There are lots of good aftermarket coolers out there. Decide whether you want a big heatsink or a closed loop, then look at reviews to find the best for your use.