Prior to Windows 95, I believe all point upgrades were paid upgrades. Though there wasn't a universal medium to provide free updates like we have today... it was the "drive to CompUSA and get a box full of disks".

Between Windows 95 and Windows 2000, there were many updates in between that didn't have a cost difference, but also didn't have a direct upgrade path. I worked for a company that supplied and supported small business networks, and I recall that many of the OEM upgrade versions didn't even provide a way for regular users to get their features. The initial version of Windows 95 was released without Internet Explorer. When OEM Service Release 1 (OSR1) was released, it included it. Regular users could install Service Pack 1 and Internet Explorer separately giving them the upgrade to OSR 1 for free.

Windows 95 OSR2, OSR2+USB and OSR2.x did not have an upgrade path at all, nor was there a way to purchase the full version outside of the OEM program at full OEM pricing (regular users could do this by buying enough of the system components to qualify the purchase as a build, but I believe they only sold the licenses in quantities of 3). This was a big problem for regular users since the OSR2.x upgrades added FAT32, USB support, AGP and a few processor instructions.[1]

The service packs released for Windows 95 didn't add many of the features that you could get via the OEM Service Releases, but they did provide service pack upgrades for free.

Windows 98 had two versions, 98 original and SE (second edition). I wasn't building systems during the late 90s and a brief Wikipedia search yielded no answers, but I don't think SE was a free upgrade. The naming of this was annoying, since they started the trend of creating operating system editions like "Server" and "Advanced Server". Windows 98 and Windows 98 SE weren't different editions so much as SE was Windows 98 point 1.

Windows 2000 through Windows 7 continued the trend of free service packs. The "Editions" mess turned from a couple to a litter. Edition upgrades came for a fee, but they were different than in the past in that they were released at the same time, but certain features were only available in more expensive editions.

Microsoft also went back and forth on whether or not Service Packs would "add features" or just "fix bugs". I remember every time we had an MS rep in and this topic was brought up, they'd indicate that they didn't like the trend of adding major features in service packs, but invariably, they would add major features anyway. Windows Update and major other security features were added as part of service packs for Windows 2000 and Windows XP. Windows Vista Service Pack 2 made the operating system usable, with the addition of the bug fix (or feature) of being able to copy more than 65536 files using Explorer per reboot.

Having used Windows 8.1 since it was released to MSDN, my feeling is that they've greatly improved the operating system. I didn't hate Windows 8, though I rarely use the Metro apps, however, there are many things about Windows 8.1 that work the way I would have wanted them to work in 8.0. One could argue that they "fixed bugs with the UI", but really, they overhauled the most fundamental component of the user experience of their OS, the Start Screen. Icon behavior and features are different, the search screen works wildly differently (a plus in some cases, a negative in others). Returning the Start Button to its original position, was a huge improvement despite my initial skepticism that it would make all that much of a difference.

[1] http://en.wikipedia.org/wiki/Windows_95 and from memory.