Use thermal paste, if not for performance, at least for peace of mind. Get a tube of Arctic Silver 3 and it'll last a while.
If you aren't gonna overclock, the retail fan will do, but it doesn't hurt to spend a little extra on a nice HSF. I bought the Alpha Pal8045 about a year ago b/c it gave me OCing headroom, but also b/c it can be fitted with a much lower rpm and quieter 80mm fan. There are lots of nice copper HSFs for really cheap now, I think the Thermaright SK-6 is quite cheap now as well. The only considerations you should have if you don't plan on overclocking is the noise level of the fan and also the mounting mechanism.
Chiz