Launchy, the famous open-source keystroke application launcher, which was previously available for Windows only has now made its way into Linux too.
Launchy is a free utility designed to help you forget about your start menu, the icons on your desktop, and even your file manager. It indexes the programs in your start menu and can launch your documents, project files, folders, and bookmarks with just a few keystrokes!

Apart from only providing easy access to all applications, Launchy also allows you to search Google, check Weather, Do Calculations and lots more.
Launchy can be downloaded from SourceForge (To install on Ubuntu, select the .deb package for download)