On Start menus, program lists, and keyboard entry
Back in the olden days, there was the command prompt. Command.com, BASH, I don't give a damn, that distinction doesn't matter here.
Then came Windows. Because of some sort of legal tomfoolery with Apple, Windows 1.0 didn't allow overlapping windows, except for dialog boxes. They were either maximized, or automatically tiled together. This is important. There was also no Program Manager yet - only a sort of prototype File Manager, the DOS Executive, to start your programs with.
In Windows 2.0, windows became unhinged, and it was pretty cool 'n all. Not much else that matters here had changed.
In Windows 3.0, the Program Manager was introduced. You now had a bunch of group icons inside ProgMan, each with a bunch of application icons inside them. Disk capacities were still nothing impressive back then so you could only have so many applications installed, and as such, only so many groups.
In Windows 95, the Start Menu replaced ProgMan in purpose. You now had your groups as items in a Programs menu, and they were much smaller than the icons. From 32x32 icons with the caption below them, they went to 16x16 with the caption off the side, so you could fit way more items on the screen than before. With growing disk capacities, this would seem like a pretty slick move.
Congratulations. Instead of a bunch of doubleclick-to-open group icons, you now have hover-to-open menu items, which can contain more subfolders of their own because it's based on an actual directory structure, and soon enough your list grows taller than the 600 or so pixels you had at the time and breaks into a second column. And a third, in time. Good luck finding that program you wanted now.
In time, popular programs would appear in the start menu proper, leaving the masses in the Programs item as always. In time, you would get to pin your most popular programs there. This does not, in practice, solve anything.
In time, a search field would be added, so you could just type the name of the program you wanted, wait a moment for it to be identified, and hit Enter.
Congratulations, you're one foot back into a command prompt.
Linux went through a similar evolution with regards to start menus and lists growing big. Recent distros categorize each application -- Internet, Games, Education, Programming, Graphics... enjoy finding that one game in a list of hundreds, all listed under one category. What's that you say? You have a search field?
Congratulations, you've almost made me repeat myself.
What I'd do is put the other foot in there too. Windows lets you do shell replacements -- it's been possible from the very beginning, considering how they replaced DOS Executive with Program Manager with Explorer (which is not only the file system browser but also the desktop icons and taskbar) -- and anybody who's good enough at it can write them. Just look at projects like SharpEnviro or bb4win. So why not take out the task bar and start menu completely, take the desktop that remains, and put a fullscreen console on top of it? Have the desktop image shine through, because that's what they're for. The actual application windows don't need to change. They don't even need to know anything about the shell replacement in the first place. They can look and feel just like before.
Instead of slogging through that huge multi-layered list of program shortcuts, or typing program names in the search field, why not just go full circle? The new Metro UI already all but throws away the last 25 years of UI development anyway.
Yes, I know tablet users wouldn't be able to use such a shell. But most tablet users probably wouldn't know how to install a shell replacement, if even that it's a possibility.