AVG AntiSpyware Free will add something Norton doesn't have. It's made for antispyware purposes only, and is therefore, in my opinion, a better tool when it comes to detecting and removing spyware. I think its a very good scaner and cleaner. The pro (costs money) version includes live protection against spyware, but most people doesnt need this, so I wouldn't recommend it.
Most people would recomend Spybot and/or Ad-Aware (both free) as well as AVG Antispyware (I've got all 3) because no program finds everything.
(Haven't used AVG free and Zone alarm, so I cant tell you anything)
If your PC boots slowley, I would recommend
Winpatrol free as well. Winpatrol is a user friendly program, that you can use to delay the start of unimportant programs. It also detects all the changes to startup programs (if a new startup program is installed), so if you decide to donwload it, you should install it after you've installed everything else. You can see some reviews
here.
AVG Antispyware (and SpyBot, Ad-aware and Winpatrol) are programs you can download and install right away with out interferring with NIS. When it comes to AVG free and Zone Alarm, I think you should donwload first, then remove NIS, and finaly install AVG and Zone alarm. However its possible to deactivate NIS, so perhaps you should deactivate, install AVG + Zone Alarm, and then remove NIS? I guess the guys you talked to in may knows what to do, so you'd better wait for them.