When doing a fresh install, I have to be behind a firewall. I've seen a new W2K machine infected via a viral probe minutes after it first connected to the net, before the patches could be applied.
I've hooked up IP logging for attempts for incoming connections and they pop up on a regular basis.
In my laptop, I have a PFW, A/V software, the hosts file from mvps.org and I install patches as soon as they come out. And I pray.