I wonder how hard it would be to eliminate setuid (including POSIX capabilities) entirely?
[ find -perm 4000 ... ]
Looks like most setuid binaries could be replaced by services (e.g. over D-BUS), running in an environment that is known and trusted. e.g. chsh, ping, mount (for cases where setuid is used), passwd, at.
su and sudo could be replaced by ssh (or telnet) localhost.
I'm not quite sure why chromium-browser-sandbox needs to be setuid, but presumably a slightly improved seccomp mode would fix that.