Personally I would be fine with unsigned apps requiring the user to click through a notice before install, or having a setting to toggle to enable unsigned apps. Windows does something similar to this where unsigned binaries get a pop up warning but signed ones are executed immediately.
Obviously this is going to impact the supply of apps, since the market share of custom Android is smaller than even the market share of people willing to sideload or use an alternative store on a mainstream Android phone. Many developers might quit the game.