Finally we come to the restricted shells. The most popular, rbash, is a restricted bash shell. Setting a user's shell to rbash will provide absolutely zero security. In theory, rbash will prevent users from running anything by specifying a full path, including './' (the current directory). This implies that it's difficult for users to run commands, including scripts they write or downloaded exploits. Since $PATH is controlled globally, users can only run things in those locations. Unfortunately, /bin/ is going to need to be in their path, so all a user needs to do is run a new shell, and rbash is no longer in the picture: 'exec bash'
One method of alleviating this is to give users only one item in their path, a directory the administrator created. Within the directory, simply place symlinks to all the authorized commands. This is nearly as cumbersome as setting up chroot, but much more tolerable.
There are certainly ways to prevent users from running downloaded programs, but in the end, the multi-user security of a system will depend on security of every piece of software installed. Preventing the exploits from being successful, a la SELinux, provides the most viable method of protection. Coupled with a frequently updated system, additional restrictions such as rbash aren't generally necessary.
The real takeaway, though? Security isn't convenient, and if it is, you're doing something wrong.