There's still a lot of room for improvement. Starting with more consistent metadata and systems to get rid of folks spamming keywords into their descriptions and other stunts. Reducing robot reviews would be another nice item.
And it's not just the App Store, it's all stores. Metadata in the movies etc also sucks. You have soundtracks connected to the wrong item, you have actor searches not pulling up items someone was a major figure in. You have a lack of connections between genres. Take for example Tom Felton, the blonde kid from the Harry Potter films. He's only listed in like 3 of the 8 films and he was a pretty major character in the series. He's also a musician and has had songs up in iTunes for like a year and only recently did they show up if you hit a link with his name. Another example, Stephan Lang from Avatar. His handful of tv show guest spots don't show. Only in the past couple of months did links to is long list of audiobook narrations appear. but if you hit one of his actor links you also get books written by a J Stephen Lang which is not the same guy. I could find other examples as well but you get the idea