Setting up a VPS from scratch taught me a great deal, it's nice to be able to flip a switch and make all your mistakes disappear, and then have a new fresh canvas available.
Of course the skills you learn are more sys admin / OS concepts than fundamental CS concepts though.
Probably something like "Linux From Scratch" http://www.linuxfromscratch.org/ would also be a good way to learn the important details.
I'm currently using Ubuntu as my primary OS at home but I will give Gentoo a shot.
I moved to Arch after a few years with Ubuntu and I love it. It's a little higher-level than Gentoo in that you don't have to make your own file system or compile your own kernel, but it is an educational experience in that you have to install anything you'd like to use. When the 15 minute install is complete, all you have is a bash prompt. Getting a GUI, the ability to print, wireless, etc is all up to you.
They give you a great package manager and they maintain an excellent Wiki that can walk you through almost any task. Arch taught me loads about configuration.
Then again, I did Gentoo back in the day too. It might take 4 days to complete the installation, but you sure will learn some things! :D
They both can deliver you to about the same point on install (Gentoo stage3 install).
If you do it in a VM or on a spare machine then you will have convenient access to web resources, which you will need :)
Start here: http://www.gentoo.org/doc/en/handbook/handbook-x86.xml?part=...
The thing that is different about installing gentoo vs centos or ubuntu is that instead of something that looks like this:
You get a walkthrough of what fdisk is, then how to use it, then you use it to partition your disks. Instead of selecting a filesystem from a dropdown, you make one with mke2fs.I don't recall if Ubuntu even tells you what lilo or grub is.
The reason I like this is that it forces you to understand what is going on. What is the /boot partition? Why is that important?
Installing gentoo is going to force you to use tar, and wget. It's going to force you to get comfortable on the command line.
It's also going to force you to understand what a kernel module is. It's going to force you to understand things like: what chipset does my wireless card use?
It's hard. And it takes forever. And it probably won't work the first time.
To me, it's kindof a rite of passage, like telling a carpenter that he has to build his workbench before he is allowed to start working on anything else. The workbench he makes might suck...hopefully this causes him to want to keep building new workbenches until he has one that is perfect.