Ian keeps bugging me at how great Quicksilver is. Knowning that there must be an alternative built for linux, I accidently stumbled across Katapult.
While it still has a little room to grow, Katapult makes a great tool in any KDE toolchest. Press ALT+SPACE, and your widget fires up, ready to take your orders. Since words don't really do this justice, I created a screencast.