I can maybe contribute a few things here:
Puppy Linux is a great small distro, however the layered file system can be a bit tricky to work with when using a persistent install. Also it uses lilo boot loader which has caused me problems in the past when grub was previously installed. I would not recommend puppy on a system that previously had grub unless you are comfortable editing the boot record.
Slitaz is a really great low end option. In the same vein I would recommend antiX Linux, a mepis variant. The project was defunct a few years back but has since been picked up. I haven't used it since the new developers picked it up, but it was fairly fully featured and easy to use when I tried it.
Another possibility would be to use a stripped down version of Debian or another big distro. I've heard of people using a bare bones version of Debian as a router with as little as 32mb ram.
As far as the smallest, I think the title goes to tiny core, a 16mb fork of dsl which is still actively developed. The package manager is a bit clunky compared with something like CentOS, but it is startling what can be done with such a small amount of disc space. There is a port of TC called picore designed for the pi.
If you have a computer capable of virtualization, I would recommend you install virtualbox or other virtualization software and test out some of your options to see how they feel in order to make a good choice.
A great place to research options not mentioned here as well as what is new and being currently developed is
http://distrowatch.com