I haven't browsed the App Store in a while, but what happened to a section for listing all new releases? It seems that the only apps I can download now are Apple recommended apps.
You used to be able to see all the new releases (not new and noteworthy, actually new apps as they were being approved and going live) in each section of the app store on the iOS version of the store. But that has since gone.