In Add/Remove and/or synaptic there should be a section for recommended applications, the recommended applications could be submitted/voted in by the ubuntu community
The problem with #3 is that the stars are not particularly informative. They give very little information as to how popular an application is relative to another.
Why not have a sort of developer's list of applications for each category depending on what flavor of Ubuntu you are running?
Let's say you are using Kubuntu and you want an application that is in a category, but don't know which application works well with KDE? Then you could view applications that the developers recomended for KDE and install them, sorta like packages the developers decided would work well with Kubuntu but didn't have enough space to include them. The same could be applied to all other Ubuntu flavors.
So if you have Xubuntu and want a lightweight word processor you could just look at the list for Xubuntu under the word processor category.
This could be integrated into Add/Remove and Synaptic.