In ubuntu and other distro you can easily search and install software.
This much we know.
What if you were to list all the available software in the menu system as if it is already installed.
The user selects a program from the menu and runs it.
Ubuntu then installs the program if it isn't already there and runs it for the user.
Perhaps will need a new approach to the menu layout and merge the use of a search in the menu.
Also maybe a "Install now?" dialog to give the user the chance to change their mind -due to disc space or something.
This is the sort of thing Linux could do which Windows can't and would show the use exactly how much software IS available at the touch of a button.
The user is just doing what they have always done (i.e. just run programs) but it extends this to installing extra stuff too with little extra thought.
You could even put fake entries in the menu for programs titles which are popular on Windows and install and run the equivalent.
This could be backed up by a community website to create the fake entries based on user requests for Windows software and the menu system could access the site (XML based or something).
I'll stop there. :-)