I think i have an idea that would better protect normal users while not getting in the way for power users and developers:

1. All applications must be signed with a valid store key.

2. Anyone can import a store key after rebooting into the bootloader (similar flow as custom roms)

3. Google can maintain a list of malicious keys and reject them

Why is this better? Because it makes it much harder to trick grandma into installing an APK some site just dropped.