You need to use a SSD instead of a HDD for your OS. I can cold boot and have the desktop/taskbar icons, including AVAST's, up and working in under 45 seconds.
You'll be amazed at the speed difference a SSD has on startup. You can still get delayed icon appearance although in my case it is not AVAST.
I've always been interested in the order and the speed the taskbar icons load and what is controlling it.
For me it is a Realtek HD Audio Manager one that is the slowest. Yet I have another PC which was set up almost identically with the same OS, programs installed in the same order but they appear in a different order in the taskbar and there's no similar delay for that icon.
Only difference is the second PC has the same make but different (actually older) generation MB and drivers.
BTW uninstalling (thorough) and reinstalling programs only change the order temporarily, on reboot/restart they're all back in the old order. But why there is a noticeable delay in comparison to the others for just one icon, whatever that is, I have no idea.