Locking down is more an administrator thing than a distribution one. No amount of locking will do any good when they can drop in a CDROM and hit F12 on boot, after all -- that's something you have to think of and prevent. And no distribution will come with a kernel built to match your machine and exclude any device drivers for hardware they don't absolutely need.

Use the old grub-0.97 bootloader for loading. It's much simpler to configure than the new one when you have a static disk layout, and can be locked down pretty thoroughly.

Use a distribution like Gentoo or Slackware where you you get what you install and ONLY what you install, no more, no less.

Build your own kernel. Exclude any and all device drivers for things they shouldn't be using. If you give them a PS/2 keyboard and mouse, you don't even need to enable USB!

Make /tmp/ its own partition, with the 'noexec' flag given in /etc/fstab so nobody will ever be able to run executables in it. Come to think of it, do that for /home/ too.

Make their home directory and profile files read-only and owned by root. That way they can't alter, delete, or replace any config files, and won't be able to download into it. ~/.firefox/ or what have you will have to be writable, though. Make their login shell a restricted shell, /bin/rbash. If they ever get into a shell login somehow they won't be able to do anything useful with it.

Don't give them Java if you can avoid it. You can make an ersatz anything in Java.

Alter /etc/inittab to not spawn terminal logins on VT1-VT6. This will prevent them from doing ctrl-alt-f1 and getting into a raw text console.

Don't install a big WM like Gnome or KDE which will come with thousands of apps and built-in security holes for user convenience. Install something small and predictable like Fluxbox. You get easily-configurable menus and no bundled programs.

And lastly, secure the machine itself. Put in a BIOS password, prevent booting from external media, disable the PXE boot ROM, stick a good padlock in the little loop that prevents people from opening the machine, etc, etc.