This suggestion is based on the accordion style menu. With the current design, you can't switch between "departments" without going to the main department screen. I know it's a tiny thing, but I find kind of annoying. I suggest something like this:
My accordion styled suggestion
You could argue that this UI would be unfamiliar or too complex for many users, but with everything being animated with Clutter, I'm sure the animations will make it easy to understand. This accordion concept is also very common on flash websites.
The department screen, which is displayed at startup, would not show any applications (only the departments) since no department is yet selected. This also means that you can search all departments from this screen, just like you can with the current Software Center UI (see the first screenshot above).
If you're already in the, let's say, games department, you can simply click the orange bar to return to the department screen, which would close all departments to look something like this:
These mockups doesn't include all departments represented in the actual Ubuntu Software Center, since this is merely a proof-of-concept.
Please add your feedback and comments on this site or on the Software Center comments wiki.