I've used AdAware and Spybot S&D for years, but I hear Webroot's software is supposed to be the best right now. You have to pay for that, though.
HijackThis! is a low level program that is highly effective, but you must know what you're killing before you do it. If you shoot yourself in the foot with HJT, you wind up blowing both legs off. You really should use a forum where the members read stuff like that and tell you what needs killing...there's several of them around, but I don't remember where...just Google it.
Also, Matt (Charon) and SparkStalker are also very helpful in this regard, so you may want to post about this on BONR.
As for an ISP, try to use a local mom and pop if you can find one on a local number. You'll pay more, but it's a lot simpler and you can get local help when you're stuck.