For me these two were the only improvements in the user interface of Windows 95, but they were indeed very important. There has been no other user interface element of Windows 95 that I have considered useful and which I had not already used earlier.
The Start menu offered a much more convenient alternative for starting programs than starting them by clicking icons, like in the previous versions of Windows.
Nevertheless, I cannot understand how it was possible to patent a "Start menu" when it had only trivial content modifications in comparison with the menu used in twm, some 8 years earlier.
The second improvement was the auto-hidden taskbar, due to which the minimized windows no longer wasted screen space.
This is the only user interface element that I had not seen before using Windows 95, so perhaps it was patentable, even if it is a pretty obvious solution that could be found by anyone in the instant when it was recognized that the screen space occupied by minimized windows is a problem.
This is a general problem that affects many patents which are the obvious solutions for some problems and they do not require any kind of ingenuity for their discovery. The only reason why they are novel, is because those problems have not been encountered earlier, so nobody had thought to patent solutions for them.
So I believe that with the possible exception of the auto-hidden taskbar, it should have been easy to fight any claims of patent infringement by other graphic desktops, because for all features the differences from prior art were trivial. If the story from the parent article is true, then perhaps RedHat and al. have been scared by the legal expenses so they have chosen a workaround even if most Microsoft claims should have been invalid.