This depends largely on what apps are already installed and also on the existing network settings. Sometimes if you're using DHCP, the boot time can be increased dramatically if your DHCP server takes a long time to respond. You may want to experiment with booting without an installed network to see if that changes anything. If it does, then you may want to assign a static IP address that doesn't conflict with another machine on the network.
This was first published in May 2002