This might be a terrible idea, but is it possible to have non-installed packages automatically installed? That is, instead of seeing this:
$ git clone ...
The program 'git' is currently not installed. To run 'git' please ask your administrator to install the package 'git'
Seeing this instead:
$ git clone ...
Installing package 'git'
...