A freemium model is viable. You can't have ads or ad-tech tracking, or you just end up another Google. But you can have free anonymous use, and paid pro or business plans (API use etc). And referral link attribution can be done anonymously and with no commercial influence on search results.
I also think you have to share any revenue with the people actually making content fairly. That's one of the worst things about Google, and it's one of the reasons the entire media landscape has become an ad-tech nightmare, because Google and Facebook take the lion's share of digital revenue.
It's worth trying other approaches. Ads are a corrupting influence. If you don't say a hard no to them, they eventually take over.
But it's not - if you're happy with your potential userbase being O(millions) instead of O(billions), charging for your service is completely fine.
Google wasn’t the first search engine, and I expect it won’t be the last. Page Rank redefined search, and now that results are 95% advertising-driven, the underlying “search algorithm” means nothing at all. Someone with a “new” algo that isn’t so completely ad-driven (until they too succumb to the only existing model for revenue) could un-seat the giant, at least maybe in search.
This is the curse of the advertising model for all things. Though it can make a lot of money for a good long time.