NO NO NO on the soap and water method!!!
Rubbing alcohol would work fine. Just take your time and go slow. If you got little ramsinks that have thermal tape applied, no, you do not need thermal paste.
As for your thermal paste on the GPU, just dab a little in the middle, get a plastic baggie, stick your finger in it, and dab it around on the GPU into a thin, even layer. You should still be able to see the GPU, as in a somewhat-translucent-thin layer. You really just want to avoid the giant 'toothpase' glob/application scenario. If your new GPU cooler has the pre-applied thermal paste 'pad' either peel/wipe it off (no scraping) and apply your choice of thermal material.