Comment 1 for bug 860536

The "Open With" > "Other Application" dialog already has a "Find applications online" [sic] button, which opens a broken dialog listing applications. (Broken because it doesn't actually let me install any of them.)

I think a solution to this bug involves (1) replacing that dialog with a mode of Ubuntu Software Center and aptdaemon (so that it knows to try opening the file once an application is installed), and (2) altering the dialog that appears when you try to open a file where Nautilus has no idea what to open it with. Unfortunately I can't evoke the latter dialog -- everything unknown tries to open in Geany or Gedit.