It is difficult. The way Java does this, with the protection relying solely on the correctness of the runtime (the interpreter isn't emasculated so flaws in the runtime can cause unexpected behavior) it is nearly impossible. Humans aren't good enough at designing systems this century.
One thing that I'm sort of fuzzy on is whether or not you feel that this is a problem specific to this one group of products (java) or if it's a problem with the general idea of grabbing and running applets indiscriminently in a protective environment. As some recent posts here have shown, when people start working with java applets, subtle problems (like not being able to put your hands on enough entropy) emerge. It may turn out that after a year or two the list of complaints will be long enough that a demand for a successor to java will emerge. I would have to think that after a bit of practical experience, it will be possible to build a better java. Right now, as near as I can tell, we have two major security complaints with java's design. The first is Perry's point (which I might be munging), that there isn't enough redundancy in the security to protect us if and when human error creeps in. The second is that a rigorous formal analysis of the language hasn't been performed, and that the language as it is currently constituted doesn't lend itself to such an analysis. Can these problems be solved, at least in theory, in a new language? Are there other changes that ought to be considered? Etc.