One of the things I like best when using OS X is the Spotlight tool. You can click a magnifying glass in the corner, and search for apps, files, anything. Windows 7's Start Menu search tool is similar. Does Ubuntu have anything like this?
Gnome Do has some similarities, but it's really more about doing things than searching for things. Something with a panel applet like Spotlight would be ideal.