And how can you implement subscription without tracking? A subscription-based search engine, or a video hosting website, would need to connect your searches and watching habits with a credit card.
The tracking necessary to process payments is reasonable as-is but you could also pay cash for gift-cards that work just like credit cards. Either way that's nothing like the tracking that happens for targeted advertising.
The page rank is not the only possible strategy for effective search.
Google's massive patent arsenal disagrees with you. I imagine many common and obvious search methods have a government granted monopoly due to our corrupt patent system. Even Microsoft, with a massive patent arsenal itself, couldnt work out deals with Google and gets sued now and again:
http://www.theinquirer.net/inquirer/news/2240889/microsoft-g...
How can Joe Startup compete in this space?
When Google was picking up steam back in the early 2000's it seemed wonderful because there were so many immediate benefits. Now, 10-15 years later it's clear how much power we gave them and what opportunities we lost in doing so. Instead of "free" stuff we could have worked towards a model of privacy and reasonable subscription fees where user-tracking and advertising weren't the default business model of the internet. But we didn't look ahead, we just said "Give us that shiny new thing!"
I hope I'm wrong but Uber looks the same to me, it's that nagging feeling of somebody's gonna have to pay the piper.