I think you will be happy with this. Its called Cardapio. You can use the "super+space" and call the menu then search and run. It has a full menu plus web results, commands and software availability.
Installation in Ubuntu
Cardapio can easily be installed in Ubuntu versions 10.04 (Lucid Lynx), 10.10 (Maverick Meerkat), 11.04 (Natty Narwhal), and 11.11 (Oneiric Ocelot). To install, simply follow the steps below:
1) Run these commands in a terminal:
sudo add-apt-repository ppa:cardapio-team/unstable && sudo apt-get update
2) Now pick one or more of these, depending on how you want to use Cardapio:
$ sudo apt-get install cardapio-gnomepanel # <-- to install the Gnome-Panel applet
$ sudo apt-get install cardapio-docky # <-- to install the Docky applet
$ sudo apt-get install cardapio-awn # <-- to install the AWN applet
$ sudo apt-get install cardapio-gnomeshell # <-- to install the Gnome-Shell applet
$ sudo apt-get install cardapio # <-- to use it in stand-alone mode only
3) Done!
To search for files in your computer using Cardapio, you need to install Tracker 0.8.7 or above. To install it on Ubuntu:
sudo apt-get install tracker
Try to give you an idea of what the program looks like
This image is how it is incorporated into docky. If you click on docky the cardapio menu pops up.