You can still buy Android phones that have manufacturer support for unlocking the bootloader. Once that's done obtaining root is trivial. Pixel phones notably support this. Personally, I only buy phones I can unlock the bootloader on to show the demand for this feature. It doesn't matter to me how great a phone is otherwise. Can't unlock the bootloader? Not buying it.
That said, I completely agree with you. We all pay for and own the hardware, but let the manufacturer dictate what software it can run. That's like buying a car and letting the car company tell you what roads you're allowed to drive your car on. I don't really blame the average use for not giving a crap because end users will never care about this stuff as long as their basic needs are met. It's a failure of the people in the software industry to stand up for the open systems that built everything we have today. Without that constant fight for openness companies are going to be more than happy to take advantage of a locked down system to create a competitive advantage. Hell, look at what Google is currently doing with WEI in Chrome. If they have their way, the web will become just as locked down as smartphones are now.
Android was initially built on Linux
For the record, it still is.