Slackware 9.1 install= 30 mins and 1 reboot, Mandrake 9.1 install= 40mins and 1 reboot, Win'98SE install =1 hour and 8 reboots (I actually counted them). Mandrake was the easiest (does the partitioning for you, if you want or don't know how). Slack is fast, fairly easy (selects defaults for you if you don't know and also explains the choices too) although knowledge of partitioning required. Windows..... frustrating (half of the time it can't find it's own files or drivers to configure something) crashed on the 5th reboot.
These installs were... Slackware on a Celeron 2.4G system and installed Mandy on a Duron 1.2G system and Windows '98 on an XP1700 system. Haven't done a Knoppix HDD install yet but will get around to it one of these days. Running Knoppix off the CD= Bootup in less than 5 minutes and 0 reboots!!
The point is that I haven't had any problems with the Linux installs. Perhaps I'm just having good luck. They run perfectly fine with uptimes of 6+ days at times (with only a couple of program crashes..nautilus ...somewhat dislike nautilus).