Synapse
Everybody likes launchers, right? Well if you find it just a bit too cumbersome to look through a menu or folder, give Synapse a go. It is incredibly responsive and finds what you are looking for very quickly due to its heavy integration with the Zeitgeist framework.
For the more paranoid user, this could be something of a nightmare as Zeitgeist logs your file and application usage habits. Personally, when it comes to productivity, I find it's worth the trade-off simply due to the amount of time it saves.
More info Synapse
Synaptic Package Manager
Synaptic Package Manager used to be a standard feature of Ubuntu until it was supplanted by the Ubuntu Software Centre and while it is now easier to find and manage software, the selection on offer is more limited. Indeed, there's still no replacement for Synaptic if you want to run software from third party sources or manage those that you have installed manually.
Whether you want to do something obscure – like downgrade a package or simply view the changelog – there is no reason that the first application that you download from the Ubuntu Software Centre should be anything other than Synaptic Package Manager. ®
More info Synaptic Package Manager