For me, Ubuntu 9.04 already boots in under 20 seconds. I'm at the login screen 18 seconds after pushing the power button (so that includes the time BIOS still has control). I'm using a pretty low-end laptop.
Clueless help-desk techs often count "boot time" as the time it takes for you to boot, then log into your account. Then when you follow their instructions and call them back "after it boots" they get irate at you for making them wait another few seconds.
