The solution would be a "noob mode" that disables sideloading and other security-critical features, which can be chosen when the device is first turned on and requires a factory reset to deactivate. People who still choose expert mode even though they are beginners would then only have themselves to blame.
This should be voted higher, it quite literally is this simple.
This is just a variant of the "complicated unlocking mechanism" I was talking about. It still screws over everything not coming from the play store because the installation process for them essentially becomes a huge hassel, that even involves factory resetting their device, that most people won't want to deal with.