If you are new to Linux, like me, try Red Hat 7.0. It is the very latest kernel, available on CD or download. can get at auction for $3.98 + $4 ship.
Mandrake is good also. I had trouble partitioning with mandrake 7.0. Went to RedHat 6.2 and did not have the same problems.
You need to know how many partitions you want to make and the size of each before starting. Also what kind of installation (workstation, server, etc). Choose the one that gives you the most flexibility if you want to set up your own partitions. If not, choose the simplest. It will do partitioning for you.
Be SURE to back up everthing. You are very likely to loose some software if you find you have to change a partition size.