One solution would be giving apps an option to add a remote and install the required runtime from it, but Alex sees that as a potential security issue.
Can you elaborate? What security issues? Could installing runtime X subvert runtime Y used by other apps, e.g. by claiming that X is an update for Y? In that case I'd expect that GPG keys have to match, or something like that.
If the required runtime were not in one of the trusted remotes, the user would be told that the runtime was not found in trusted remotes and he'd have to install it manually before installing the app.
How is this fixing the security issues? Most users will happily confirm a dialog, without studying key fingerprints etc.