Based on the posts above, I'm astonished by how potentially ineffective Linux firewalls are, as opposed to Windows ones.
Sandbox execution, otoh, can make the engineering effort for an attacker very high to impossible: that's the way I'd go. It's what Google are doing with Android, and it seems pretty bloody obvious as a solution.