Windows Vista (and many other modern OSes) cheats during boot up. They often show the desktop prior to the OS being fully started. Some services, including networking related ones may not be fully running by the time the user can launch a program. That program will then have to wait for the services to be ready.

It's also possible Windows Media Player is starting a service on it's own the first time it runs, and repeated attempts don't have the delay associated with that. Any service marked manual can be started by a program if it is needed. Based on your comment that this happens the first time at any point, this is more likely to be the cause then my first explaination.

Also
http://www.google.co.uk/search?q=windows+media+player+deleted+my+music
oh, wait, that's the wrong search. ;-)

http://www.google.com/search?q=windows+media+player+slow+first+time