Without that fraudulent marketing, Android never would have crowded out other options so quickly in the marketplace.
The solution is to either have Google back down on breaking its promise that Android would be open or to have an antitrust lawsuit strip Android from Google's control.
I was part of this problem. I've accepted what Apple is doing because I had Android. I didn't think they'd come for me next so I didn't speak up
Not a legal argument, since Apple never claimed the iPhone was anything else but a walled garden, and walled gardens are legal as long as you are clear that users will be buying into a walled garden from the start.
(For example: Nintendo, PlayStation and Xbox)
Legally, the only thing you could do is change the law to make walled gardens illegal, as they did in the EU.
The changes Google has proposed for sideloading are illegal under existing law, since Android was sold to consumers with the promise that it was the "open" platform that allowed users to run anything they like.
Legislation, as you say, seems like it'll be necessary :/
When you chose to create an open platform with multiple participants, you are creating a new open market where antitrust laws will apply... even to you as the platform creator.
Microsoft, for example, was found guilty of antitrust in the personal computer market long after the original computers running Windows were gone.