You definitely should use thermal paste b/t your heatsink and cpu ... ie. no matter how well you 'lap' (ie. sanding with fine sand paper to get a mirror like smooth finish) the bottom of your heatsink, there will always be small/tiny gaps (this is where 'conductive' thermal paste will aid in more efficient/effective heat transfer from the cpu to the heatsink). Therefore, it is NOT recommended to go heatsink to cpu without using any type of thermal paste in between. Not very efficient that way.
Arctic Silver is the best but expensive. Any type of thermal 'paste' is much much better (and last longer) than that thermal tape crap.
Heatsink design can make a big improvement in heat dissipation off the cpu. Copper core (preferably 100% copper heatsink) is the way to go.
Heatsink fan (larger diameter, higher rpm rating, higher airflow in cfm rating) also can improve heat dissipation. The trade off is typically more noise.
Water cooling has its own set of risks but is obviously one of the best ways to cool a system ... shear performance wise. The risks may not be worth it though (ie. leakage onto expensive components, condensation, etc).
I'd start with simple thermal paste and possibly upgrading the heatsink/fan.