Seeing your configuration, the biggest bottleneck is very likely the HDD. Skype does some incredible I/O during its startup, especially if you have a lot of history stored in your profile. Now add to it the fact that the system startup is the most I/O heavy thing your operating system will do and you have a problem.
Can you try downloading and running SpeedyFox (make sure to turn off your skype/firefox/whatever when running it) to reduce the size and wasted space of the DB, as well as perhaps defragmenting your hard disk?
It may sound trivial but I had a similar experience with Skype back when I didn't have an SSD. Even though my disk was a 7200rpm one, it still took a long time for Skype to come up and the poor disk was super busy.