I warmly recommend you to try a Debian if you have the opportunity to do so.
Debian has an excellent reputation. You can trust it, and have real fun with it!
To make your choice, you might want to have a look here:
Personnaly I installed a Woody 3.0r2 from Internet, then upgraded to Sid (Internet as well).
The first steps of the installation are using floppies (4 floppies I think).
I was really impressed by the efficiency and (very relative) simplicity of the installation.
Now I'm very happy with Debian Sid.
But be very careful, Sid is the development version (the counterpart of Mandrake 'Cooker' I think).
As of today, the Debian version recommended for a desktop PC is on the "Testing" branch.
It will give you a good idea of what Sarge will be when it is released.