UPDATE May 2007: Colibri has been supplanted by Launchy on my desktop since this post.
I stumbled across a very nice application launcher for Windows, Colibri - Type Ahead. Pressing CTRL-SPACE activates the Colibri search input. You then start typing and it displays applications that match. For example, “not” displays notepad and other apps with “not” in the title. I never need the Start menu again!
Another nice feature is the integration with Google. Press CTRL-SPACE, type “Goo”, press tab and enter your search term. You default browser then opens to display the results of the Google-search.
There are similar launchers available for Linux: the GNOME Deskbar applet (which sits in your panel), Katapult for KDE and GNOME Launch Box. The Deskbar applet has loads of features, but because it sits in the panel it does not seem quite as integrated and instinctive to use as the others (read: not eye candy :-)). Katapult and the GNOME Launch Box are both quite awesome, but in reasonably early stages of development.
I’ve got no idea what you could use on a Mac ;-)