What I'd like to see is a Start Menu Stack that remembers that last dozen folders/groups you opened in Start Menu. No typing. Click something, the entries are shown. You click one, and the Start Menu is open with that group selected but not entered. That way if the one you want isn't there, click on something close and the navigation is almost done.
Recent or frequent programs is not helpful if you want to run different programs from the same group. You run one, then you have to navigate all the way back down to run the 2nd. If it's a program that's used all the time, a different method to rapidly launch is already employed. I only use Start Menu for stuff I hardly ever use. Renavigation to the same area over and over is a pita.
Stuff like Vista Strart Menu or '7' is it's called now, don't seem to have this stack feature.
Seems like to should have been built in like 12 years ago.. but there you go.