Auto-complete/suggestions on app search can be frustrating. If I am looking for a particular app by name it's great, but if I am searching by a type of app or a free-form term then I get lots of false or less-than-useful results. A better search (in my opinion) would present a category listing or two on top of the results and then list app results.
When it comes to Genius, it's recommendations are usually just way way off, and I think it's because of the algorithm being used. The recommendations are binary: "You bought this (one app) so we think you may like this (new app). The same problem exists with the Amazon recommendation, which updates a section on the home screen based on the last couple of things you were looking at – it's too narrow and reactionary.
A better experience would be a more holistic one, where ALL your purchased apps would impact the recommendations, and the recommendations that appear on the "top" would be the ones that the system has the highest confidence. In fact, the search above would also be improved with such an algorithm (of course, Google does this with thier search results – somewhat – and it may be hard to replicate such "secret sauce."
Recommendations based on both purchases and usage (number of times the app is opened) would be better still… Of course you have to balance the benefits vs. the privacy of the user when it comes to such an approach.