I've gotten rid of noise with Audacity, but I use an older version, 1.2.6, which doesn't give all those options. Step 2 is just a slider between Less and More, and a Preview button to help you pick where to set the slider. It works pretty nicely if the noise is consistent and if I can find a patch of pure noise with no music or talk. After reading your post, I'm going to try the new version. It sounds like it's much improved.

I've also used Acoustica 2.25a, which gives you the option to create your own noise profile, or alter a profile obtained by analyzing a sample. But I haven't figured out how to use that to get better results than with Audacity.