On Windows boxes, at least, it's pretty onerous. On my work laptop (where I'm forced to use WinXP), it takes me about 30-40 seconds to get to the login prompt, and then another minute or so for all the background services to finish launching after logging in. The laptop isn't usable the bulk of those background services finish launching. I suspect that that's a huge source of this sentiment, at least among folks that have to use both OSes. We don't want this in our Linux. :-)
A lot of the problem is due to how Windows handles things. I can *try* to use the laptop, but random things keep killing the keyboard focus, and launching certain apps "too early" causes them to merely crash. (I suspect the app crashes are due to the firewall service, which I think is in the list of things started *after* login.) There's all sorts of stupid things in that delayed startup, such as the backup software throwing a splash screen up. I can only speculate on what keeps eating the keyboard focus. SMS scripts I suspect. (I get similar issues when the company rolls out patches--bizarre things happen to my keyboard focus and the whole desktop flashes.)
I haven't had similar issues with delayed services starting under Linux, since they are far, far less disruptive. Sure, the disk chugs a little in the background, but the only thing I've noticed is that Firefox might take a couple extra seconds to load. So, as a practical matter, some things *can* be started late without upsetting the user.
But, I suspect that wasn't the point. What ought and ought not to be started late is a judgment call, and the overall impact on the user can be difficult to judge without putting the result in front of a lot of users. For an apples-to-apples, this-is-the-real-thing-no-questions-asked comparison, it seems entirely appropriate to measure power-on to disk-and-CPU-idle. This eliminates judgment calls and fuzzy, difficult to measure impacts. It gives you a framework for tightly targeting a boot-time budget such as what Arjan described. You don't get to wiggle around the budget by saying "Oh, we can defer that one." Instead, you're forced to consider why it's slow and fix it.
If you need to throw a few things out of that initial boot, such as full network bringup in this example, then you can separately determine what its impact is.