I've always used a nice application on Windows XP called Launchy. For me, a real keyboard shortcut geek, this has been an absolute dream. This application allows you to use a combination of keys, like alt-SPACE to open the Launchy window. From here you can start typing a program name and you get a list of applications to launch. Without using the mouse. When you've used it some time you can launch your favorite applications with just a couple of keystrokes. A real timesaver. I can't even remember the last time I actually opened the program menu under the start menu.
On Vista/Windows 7 you can get the same functionality just by pressing the Windows button and start typing. But since I've always used Launchy I have continued using it.
On the Mac this functionality can be achived by using crtl-SPACE (default keyboard combination) and start typing. This opens Spotlight, which on first impression is quite good. Like the Windows button on Vista/Windows 7 this also searches recently used documents and other stuff. You can even change the order in which stuff appear by accessing the Spotlight settings and changing the order.
I'll try this out for a while before downloading Launchy (I don't even know if Launchy runs on a Mac).