Same for me. And then with Windows 7, when Microsoft removed the Classic style Start Menu, I went looking for, found, and started using Classic Shell. It was just icing on the cake that it works in Windows 8 and Windows 10 too. Funny how so many remember Classic Shell as the great Start Menu for Windows 8, when it was originally designed to replace Windows 7's downgrade! The feature I missed the most is the ability to cascade folders/folder shortcuts from the Start Menu. The fact that we can still cascade them from the Taskbar (where I resent the loss of space), indicates that the code is still present in Windows. I also didn't like the small, boxed in, click-navigation All Programs menu. If it weren't for those two shortcomings, I would have gladly used the built-in Start Menu over installing a 3rd-party replacement.
I keep being reminded just how much of a compromise Windows 10's "Start Thing" is. The Classic Start Menu (with the cascading menus) is almost perfectly optimized for a mouse. If they made it detect intention and open instantly on horizontal motion instead of having a fixed delay on opening submenus, it would feel even more efficient and quick. Meanwhile, a touchscreen benefits from the user being able to arbitrarily tap anywhere, while missing the ability to point and hover. The Windows 8 Start Screen's All Apps view really took advantage of this and actually was a joy to use on a touchscreen (although I still think that having the Start Screen as a dual desktop was a horrible idea).
But what do we have now? A tiny All Programs window with oversized entries that both shows a fraction of what could be displayed before (for mouse), while yet on many devices being hard for large fingers to tap accurately on. Either way, we have to endlessly scroll to see anything—much worse than the Classic Start Menu's condensed vertical menu, or the Start Screen's fullscreen expanded list of items. It's so bad that I'd rather use the Classic Start Menu on touch and the Start Screen All Apps on mouse over the newfangled "Start Thing" in Windows 10! Even with reversed roles, they are better than the compromise we have now. No wonder Cortana is so integrated—the user needs the assistant just to help them do what they used to easily be able to do on their own (like quickly finding and opening a rarely used program), before the Start Menu changes were made!