Since I started using Linux on the desktop, I've always used katapult to launch applications. However I have another machine that doesn't have katapult and (since I don't use a mouse) I've always used Alt+F2 to launch appilcations on there. Well, since installing Kubuntu Hardy Heron I notice it (it = KDE4 I think) has a funky new launcher thing that appears when you press Alt+F2:
As you start typing, it autocompletes and shows the icons of possible matches below - then you can click (or tab and arrow) to them, or keep typing until only the one you want remains. Very cute!