As long as you can make settings changes, you are omnipotent. To add remove program, you can grant sudo rights for aptitude and apt-get (not synaptic as it permits to add repositories). But this is not real security.
If you know specific resources that they need access, it is different.
By the way, as long as they can reboot and change the kernel command in grub, they are omnipotent. As long as they can reboot in another medium (USB key, Live-CD, PXE,...), same thing. If they can open the hardware and extract the hard disk... ditto. Securing a computer is not easy at all. If you just need to put enough fences around some adventurous users, you can't.
EDIT reply:
If your kids are computer geeks, there is no way with technical tricks to be sure they do only want you allow them to do, even those advertised as not-uninstallable (install a virtual machine and tor). If you look at dictatorship or at actual revolutions in North Africa, the only way the countries have found to block unwanted behavior was to shutdown Internet connexions and it seams to be insufficient. In the same way, the only thing you can do it shutdown Internet or the computer. And even like that, they can see it at friends.
What follows is not really an Ubuntu answer, but I care about children and I hope this can help. My best solution is education:
- Warn them about what they can and can't do, where are your limits.
- Acknowledge to them you can't and don't want to survey everything they do. You can log everything they do, but really, it is putting a spycam in their lives.
- Explain them what is a sexual predator and how they act. (soon)
- Show them what is an indelible trace on the internet and on social networks. Visual chats are recordable and most new computer have a webcam.
- Put a good advertisement blocking plugin.
- Oh, I didn't say it to you before, but they will go to pornographic web sites (as soon as 10-12 year old for some of them). Here your best friend (in my point of view) is sexual education before they have seen one/too much and explain that they don't have to do everything that is done there.
- If you educate them to late, it will be less useful. The good time is up to you, in function of your and their situation.
Technology is not a solution for human interaction and I hope it will never be.