I totally agree with GeneralAntilles' points about bad categorisation of packages being a fundamental problem that should be tackled first. At the moment I prefer using the maemo.org downloads page for finding applications because the only practical way to browse the App Manager is by selecting All.

However, I think Reggie's right that we need some kind of friendly-looking GUI front end for the App Manager to let newbies and casual users know that there are some darn useful and easy-to-use apps and games available for their tablet. It would be nice if every app could have its own screenshot and user review system like maemo.org/downloads, and a nice big green install link too. That green arrow is a very useful visual signal.

And echoing what TA-t3 says above, there should be sections for new apps, highly-rated apps (if a user-review system is implemented) and most-downloaded apps just like maemo.org/downloads, but built into the App Manager. These give really good starting points for people who just want to see what's out there.