Windows Media Player tends to lag for me a bit as well - I found that WMP 10 was little better than WMP 11 in terms of speeding up usage. If you don't need the newer advanced features, you could download a really old version, like 5-9, if they're still hosted anywhere on the Net. (Try a quick search for the version of your choice, but make sure it's a safe site and not spamware, adware or viruses in disgusie). That way, once you have that version, if you can put up with reduced compatibility, you should be able to find a basic interface fast, effecient and more useable.
If you want to stick with WMP 10 (which IMO is the best, despite it's lagging) try deleting unused files from your library to declutter and speed up loading times, or if possible try disabling the "store" option (i.e. Napster) so it doesn't have to access the Internet, which always takes more time. Further tweaking may help.
If you stick with WMP 10 also make sure that you keep the WMP 11 runtime, which makes the program more compatible. It shows up as a seperate item in the Add/Remove Programs list, and you'll be prompted to keep it when uninstalling WMP 11. Don't remove that unless it's causing problems with even older versions (it might - I'm not sure).
Making a few playlists will always help, so that it's easier to access the exact music you want. To help in making a functional playlist, make sure all the files it contains are in organized folders on your PC. Moving them afterwards may completely screw up their playback in the playlist afterwards, so once you start making the playlist, all files should be in the right location beforehand.
Furthermore, if you're viewing or listening to files from the Net, you'll always have to buffer the tracks and wait on the Internet. Instead, if possible, download those files onto your PC and play them from there instead. This speeds things up a lot, but takes up considerable hard drive space.
What were you doing exactly when it was lagging the most? If you let me know then I might have more ideas, so I can pinpoint the problem.