well - it depends on the category. For games/entertainment this is true, but for productivity etc, a good SEO can make a big difference ( http://www.slideshare.net/kolinko/app-store-seo-tutorial )

That's true, but their search ranking is weird and kind of broken right now (e.g. company name is indexed; descriptions aren't). It would be great if that got overhauled.