Note, it's not illegal per se. It's not illegal because of a de jure monopoly. It's not even illegal because of the number of users they have. It's illegal because Bing, Yahoo et al are not as relatively successful.
It was the same with browsers. Microsoft were hit for bundling. Apple haven't been though they've done identically the same thing. Why? Because enough people bought Android phones in the EU.
I do find it dubious that, effectively, the primary criteria for illegality is not what the defendant did but what some other actors didn't do. Seems wrong to me.
And it's true - they are. By design.
Also, Many people here seem to forget that we do not, in fact, live in a completely laissez-faire capitalistic society for good reason. Especially compared to the US, the countries in the EU do not view unfetered capitalism as a 'good and just' thing.