here it's 15 something seconds from tapping enter on grub's menu to the login prompt and I log in with KDE4's kdm on an old aspire.

Youtube is switching to mpeg4 but they are still using the flash vp6 video format which is an improved vp3, just like theora. Also the new encoder in trunk fixes most of the problems you mention.