For context they also push Google search to iOS devices (Apple gets huge amount of money for that), the same way as they pay firefox to have Google as their default search engine.
The issue though, is that for android phones, it's not a "let's make a deal, we will pay you to have Google Search" attitude. You can't make an android device integrated with Google Play app store without also having Google Search in the home screen and as default search engine.
What the EU is fining among others, is the business practice of forcing device makers that want to use the Play Store to also bundle the other service (Search).