We desperately need a Menu generator feature. We can't rely on page list and category list anymore.
We need something like Drupal menus. From inside Admin area, be able to create any number of independent menus we want, and add to each of them any post, page, category, tag, and any WordPress resource that can be accessed from a URL, together with custom HTML code with PHP and shortcode support.
Each li element and each ul/ol nested submenu would allow custom classes and id to be inserted, propagating or not to its children. With the same great support body_class, post_class and comment_class has.
I also suggest it to not be added to core. It should come as a plugin to be activated, and focused being an API, so that it can be expanded by other plugins, with new features and UI improvements. That's a nice suggestion for one of first canonical plugin!
Doing so, core developers wouldn't need to develop all those features alone. They could develop really its base and a simple UI, and other developers would use API's functions, actions and filters to implement all kinds of new features above the base plugin.