For 2.0, Michael has applied subsections to the “Games” and “Developer Tools” departments, and I’ve applied subsections to the “Graphics”, “Internet”, and “Science & Engineering” departments.
These alleviate the problem (so I’m downgrading it to Medium), but with three provisos. First, we’re using a two-pane department screen, so the full long list is still there by default when you navigate into a department. (For version 3, we’ll probably replace the second pane with an “All” button/link in the first pane.) Second, some departments — including Sound & Video, which you cite — don’t yet have subsections at all. And third, in most of the departments that do have subsections, they’re not comprehensive (especially in Games).
The last two problems are related, in that we don’t have enough data to subcategorize those items in a useful way, let alone any mechanism to populate the subcategories if we did. We've been doing an extensive open card-sorting exercise <http://usability.gov/design/cardsort.html> over the past few weeks to help us determine the overall categorization for 2.0 (and we’ll publish results of that soon), but now someone needs to do intensive card-sorting on individual departments. For example, give someone names, screenshots, and descriptions of 70 games — balanced between those currently available for Ubuntu, and those not — and ask them to put the games in whatever categories make sense to them. Repeat with a dozen more people, and collate the results. If anyone would like to organize that, please let us know.