My usual recommendation for a Linux Distribution is based on who you know that uses Linux...
If you know someone who uses a particular distro then start with that one... you will get more help that way from a close source... I think most people I know who use Linux started on one distro but moved to others once they became comfortable with it...
If you are starting completely on your own, then I would throw a vote in for a recent Mandrake (though I haven't used it for a while now)... At some point I would definitely give Debian (or a derivative) a try... it is now my favorite due to the ease of upgrade and system setup... :) but it is a little harder to start with than some of the other distros for a newbie... Better to come to it later on when you have got a feel for what you are after from your Linux box...
Hope that helps
Kim