Google’s core business is search and advertising and they have worked from the company’s inception to acquire users and customers in both, successfully, and more so than their competition both earlier in their history and later and they have developed business partners along the way who value that continued business relationship.
Making deals isn’t illegal and businesses make deals all the time. The Sherman Antitrust Act declares contracts that restrain trade and commerce illegal, but Google isn’t restraining trade: they’re paying a fair market value for user acquisition and their largest competitors both know what that price is and are unwilling to outbid Google.
Up until 2017, Microsoft even had their own deal with Apple where Siri used Bing results and you couldn’t change that (still cant’t control what Siri uses actually, but Siri is garbage). Even so, you can still change the search provider in Safari and Apple only receives money from Google for Safari users when Safari users actually use Google making this more like an affiliate program.
Your whole argument hinges on this and I fail to find a problem in it. What's OK when you have 1% of the market is, by law and reason, not OK when you have 99% of the market. It seems fully logical that that also means old contracts and behavior might need change.