if the heatsink/IHS is in really bad shape, you'll want to work your way from 200 grit paper. In most cases, starting out at 300-400 grit is fine. There really is no standard method to sand it but a lot of people like to use the figure 8 motion. Make sure the sandpaper is nice and wet. Be sure to have a piece of glass or mirror to work on b/c you want a nice, flat, even surface in the end. Any grit from 1500+ is for polishing. Done more for looks than anything else.
Hmmm, you shouldn't be getting those kind of temps even with an Intel cooler. Make sure you've used some sort of thermal paste and applied in properly. Also, what is your case temps? Also, make sure you've mounted the heatsink properly onto the socket. If it's not getting contact with the chip, that's the problem. I've once forgot to put my heatsink back on my socket for 1/2 hour and my temps only rose to around 52-53 degrees celsius. This was with OC in my sig. I have no idea why your temps are so high.
A lot of heatsinks will work well for the Tualatin. Just stay away from orb fans at all cost.
The Fop should do fine. However, there are probably better performing heatsinks out there that are similar in pricing. Hmmm, you can try the Volcano 6Cu/6Cu+. I'm not sure if their copper base will cover the entire IHS but I'm pretty sure it will. They peform pretty good considering it's a Thermaltake product. They are also relatively cheap.
There's also the WBK38 which performs well, but do bear in mind it has a 7000rpm fan.
If you want something quiet, try looking into the Millenium Glaciator II. Not sure about the cost, but I hear it's great considering the noise output. The coolermaster heatsinks are also quiet but I've heard flaky results with them.