"installing a binary that is untrusted is a security nightmare"
Mobile OSes shown you can sandbox native applications as well - it's not really that difficult, it's just what the OS APIs let them do. Java and .NET promised to sandbox applications as well, even if many ways to evade the sandbox were later discovered. WinRT and UWP applications are another example of native sandboxed applications.
The problem of sandboxed applications is their little interoperability with other ones. If the applications are wholly self-contained, say a streaming player, or a game, that's not an issue. But for applications than need to interoperate with others - say an email client that needs to receive or pass data to other applications, or the OS itself (i.e. to attach a log file...), that becomes a far bigger issue.
But you say "untrusted" - that's why digital signatures of executables are not a bad thing, of course if the trust chain is reliable.