The avast tray icon is an integral part of the avast protection, but an interface to the program settings, etc.
Avast should be running fairly soon after boot so you should be being protected, though why it isn't appearing for some time after boot isn't normal. I have XP Pro and it is one of the first icons I see displayed in the tray.
How do you connect to the internet, dial-up or broadband ?
What other security applications do you have installed (firewall, anti-spyware, etc.) ?
You can check the Task Manager and you should see avastSvc.exe, the main avast process that controls the avast shields and scanning. You may also see avastUI.exe, that is the avast user interface process and what loads the avast tray icon. Are both of these displayed in the task manager early in the boot process (check before the avast tray icon appears) ?