Shameless plug: We've got lightning-fast iOS app search on Appsfire. Apps sorted by relevance and quality (using our own App Score) http://getap.ps/appsfire

We're not there with Android yet, though.