I guess Linux users could be divided into two general groups.
The first group are the Linux tinkerers and hobbyists. Those that enjoy learning as much about Linux as possible. They are happy to fiddle with arcane configurations, try out different distributions, and generally get a buzz out of running on the bleeding edge.
The second group would be those that see the OS as no more than a tool, a reliable easy to configure tool, that is an adjunct to your main task. and not an end in itself. They want an OS that is straight forward to install, and just works.
If you are in the first group, there are a huge number of distributions to download and play with. Downoad Gentoo, if you want the latest and greatest tailored to your hardware. But expect to spend a few days compiling and configuring before you have something workable.
If you fit somewhere between the two groups, install Debian, you will land up with a fine system after a bit of tinkering.
If you see yourself in the second group, you just want to pop in a CD,
wait a few minutes for the installation to run, and have a usable system, there are really only two alternatives; Mandrake or Suse.
I have installed both a number of time on a few different laptops, all were IBM Thinkpads of various vintages. Both distributions installed flawlessly.
I have eventually settled on Suse, currently running V8.2, and I can heartily recommend it. Mandrake worked just as well, but I found it a bit too cutesy for my taste, and I think it looks a bit amateurish.
Suse has only one disadvantage, you have to purchase it, but the manuals that come with it are well worth the price, and you may actually save some money by not having to purchase 3rd party books. There is a free installation over ftp, that is more of a pain than it is worth, or you can download the evaluation version that runs off a CD but does not install.
Which ever distribution you choose, install it on decent hardware, the modern GUI interfaces are just as resource intensive as that other OS from Redmond. Gone are the days of \"throwing it on the old PC in the corner\", this only applies if you want a command line only install.
Have a look at
http://www.linuxiso.org/ if you want a long list of the available distributions.
Good luck, once you have Linux up and running, you will never look back.
Regards,
Clive