Samsung may decide to use different apps not Google ones, they may decide to use a Chromium fork with Bing as search engine so your data will not go do Google, maybe Mozilla will manage to do a deal with a big manufacturer and put Firefox as default and nobody will have to pay.
What has stopped them from doing this all this while? A shell company by Samsung renders any deals with Google impotent - a strategy used by many Chinese OEMs who have Google Android for international markets and their own app stores within China.
This is not my opinion. If you go to a VC or even YC with these claims, they will counter with the widely available data pointing towards the high probability of a third ecosystem failing.
It won't be "horrible for Europe." Those users have always paid for these apps in one way or another.