By Improving Search
Here's my 2 cents: Just by giving a bigger list of apps like Top 300 or 400 would not cut it. As again we will have a the same problem of discovery on a bigger scale.
The best solution I think is to improve their search algorithm i.e., to show results to users for what they are actually searching for, like google does. Remember the web stated like this for example: Yahoo was a directory, listing websites & categorizing them. Then came Google with its search algorithm & rest is history
So something similar has to happen with the discoveribility of Apps in the App Store