A fresh installation of Windows will get HAMMERED by spyware/adware/malware/worms. I found 3 different programs hijacking my comp right after i got past the Welcome screen on reformat/installation because i'm on a LAN router. Run your Spybot/Adaware/any other stuff, and UPDATE Windows. Make sure you have at least SP2.

Wc3 uses port 6113 for BNet, so make sure that port is opened/forwarded. Try turning off your firewall AFTER you update Windows, and see whether the lag still happens. You'll need to refer to program documentation on how to forward the port, since every program is different. Not sure about zonealarm, but i think it configures that automatically after asking you. The Windows Internet Connection Firewall is probably active too, so you'll have to kill that.