Hi guys, I've got some news. Igor was kind and mentioned that he has seen a similar issue on one of his own machines (running Windows x64 - but that doesn't seem to make any difference). So, I did some monitoring and found that the problem is caused by the "Workstation" service that hangs on startup (most likely communicating with the network stack) while holding the global SCM (Service Control Manager) lock (preventing other services from starting).
So, what I did is create a dependency of the "Workstation" service on the avast services - and voila, the problem was solved. You can try the same - chances are it will help on your machines, too.
I have created a reg file to make it simple - just import
http://public.avast.com/~vlk/avast-fast.reg , reboot the machine and see if it makes any difference.
Please note that the reg file assumes that you're using the "Web Shield" and "Internet Mail" providers, that is, that the two corresponding services are installed on started (almost always the case - unless you have played with the avast config a bit).
Cheers
Vlk