My complaint with the Windows 8 start menu wasn't that it took up the whole screen, it was that it took up the whole screen to show _the same number of items_ or fewer than the 95-style start menu. And half of them were ads.

A full-screen start menu with the same information density as the 95-style start menu, possibly with a pane for programs and a pane for explorer, is something I'd happily try out.