Well the nice thing about taking advantage of Selinux (or Smack, or Apparmor, or some desktop-specific LSM layer) is that you can apply the security contexts to applications without having to do extensive rewriting of them or whatnot.
So typically a application is launched when you double click on a file. As long as that application gets launched as a separate process then it's (relatively) easy to isolate that process and restrict it's movements. As long as the program behaves itself this should be all completely transparent to the end user and would not require any rewrite of the application, barring any bugs. That is you get the security 'for free' without bugging the user with dialogs or having applications run in a odd manner. This should work with very little impact to the end user and should apply (relatively) easily to most programs.
Now the problems you run into are programs that try to 'optimize' things by launching new instances in threads. Programs like your web browser.
The other way this breaks down is if you have a running program and you go to open up a file through the application file dialog. You can get around this by making the file dialog aware of what is going on and adding a notification to bug the user or something like that. That shouldn't be terrifically difficult for the KDE and Gnome applications, but it would be troublesome for applications that use their own file dialogs (OO.org, for example).
The other way to go about it would be trying to take advantage of some of the work going into trying to standardize the anti-virus stuff.
That is efforts to get on-demand scanning into the kernel were the kernel can intercept files being accessed and defer to a userland program, which then can allow or disallow the access.
Then you can intercept the programming accessing a risky file and then pop up a dialog warning the user.
Or you could program that into nautilus, konquerer, and the file dialogs to check that stuff..
But I don't like that because that's annoying and will be just another dialog for a user to ignore. They downloaded the file and while it may be risky they still want to find out what is in it... so by opening it in a application is the only way they could know what it really is. So your forcing the end user to make security decisions without allowing them the information they need to make the correct decision. If they make a bad decision and it's a malicious file then it still gets read into a program with full user privileges. So it's a bit of a mess.