Where I look for software, in order of preference. …
The package manager and repositories of my distribution (Linux only).
rpm.pbone.net (RPM-based Linux only) will usually find a distribution-specific RPM if it exists.
Ohloh is easy to search and gives useful metrics on the project's activity. Few user reviews, but what there are are useful.
Freshmeat is easy to search.
SourceForge has a lot of good software but is hard to search. Some user reviews are useful.
AlternativeTo is a great idea: State what application you want to replace and be shown alternatives. Sadly its usefulness is crippled by idiotic users unable to distinguish between (for example) backup vs. disk imaging, or open source vs. proprietary licenses.
Cnet (Windows only; mostly proprietary) scans its offerings for malware. A few titles are professionally reviewed, which is helpful. The user reviews are useless and can be ignored. Cannot search by license.