I don't know your previous experience with computer usage, but if you do not get scared when
you see a prompt and want some (moderate) challenge, you could try the debian system.
It is not the easiest installation, but debian has its strengths in maintainability and consistency of the system and its great package manager (imagine the joy of the fact that most of the time of that you don't have to search the web for the software you are needing). It also has one of the biggest software archives distributed within.
Still, the Mandrake or RedHat would be a safe bet from the installers perspective. Mandrake has a reputation of being (new)user-friendly and Red Hat is quite common, so that having some experience in the most popular distribution is not a wasted effort either.
If you really want to break your head with challenges, you could try the
Gentoo distribution or something as pathological as
lfs.
To get started, you should obtain a cd from the linux distribution of your choice either by buying one from the local stores. Or if you have reasonably fast internet connection you can
download one and burning your own copy.