I'm on Gentoo Linux. KDE 4.3.1 needs 9 seconds to give me a functional desktop after logging in from KDM. KDM itself needs about 3-4 seconds to appear after starting the XDM service.
Edit: If I actually left-click during the last step of the KDE initialization phase, the 9 seconds become 6 seconds. But it still takes 9 seconds to hear the login music though.
Edit2: All of this with cold caches, right after a reboot. With warm caches (just logging out and then back in), login time is only 4 or 5 seconds.
Edit3: (Too many edits :P) My system *is* tweaked though with prelink. All libs and executables are prelinked and everything has been linked with "--as-needed" linker flag enabled. But this should only provide maybe a 1 or 2 seconds advantage at best, nothing dramatic.