Mine (see sig) probably takes a minute or two to start up, but then it's also starting the wireless LAN and USB services as well. I chose this model because it supports 3G HSDPA failover (and I've needed that after lightning strikes to my DSLAM lately).
As far as startup time is concerned, however, it's really not an issue because I leave the router running 24/7 behind a UPS and ADSL line surge protector. I have a few PCs at home connecting wirelessly to a Network Attached Storage device and printer, and the router is providing DHCP in addition to ADSL, so switching it off is really not practical.