I'm a huge fan of Arch. Not only can you quickly search for packages, but the packages are actually maintained and kept up-to-date. With Arch, not only is the software usually up-to-date... even if it isn't, it is easy to modify a PKGBUILD file—but they actually provide a package search on their website.

Even Ubuntu and Debian allows you to search packages on their website, but not Fedora. With Arch, when you search for a package, you can immediately see how the package is built as well.

Yes, Arch is not a distro for people that just want to run Linux with a bunch of out of date software. It is for people that want to take some building blocks and create the perfect distro for them. Unfortunately, the choices can be confusing at times, but it has been well worth the effort on my part to find out what software works for me. Once you do that, just keep a list of the packages you install. If you need to reinstall, it is easy enough providing that package list to pacstrap.