freebsd, solaris, debian and gentoo are the three ones that I'd use in terms of server OS's. Solaris has the advantage of ZFS, which is the most brilliant file system in existance at the moment, and debian is especially great on older hardware. FreeBSD I find good for just setting up and leaving, I've never done anything complicated with it but for the bare essentials (like file sharing) it works like a charm. Gentoo is great when you want to build a really sleek, customised system from the ground up.
I think soon Linux is gonna become a serious competitor on the market, but first they need to make it more gamer friendly.
Actually, it's probably the games companies that need to make the games more linux friendly - there's good drivers out there for the majority of cards at the moment and 3D stuff that's been ported over does for the most part run very nicely.
In terms of startup times, I'm logged in and ready to work in well under 30 seconds on my box, it's only a couple of months old but it was a modest build - if I splashed out on some more fancy components I could easily bring that down further. If I used something like Gentoo I could probably get it down further still (using a stripped down Ubuntu install currently.)
Windows on the other hand... well. Let's not go there. It's not appalling, but nowhere near as quick.