Your post echoes one of the most common on this board. You will assuredly get a lot of advice about the best distro, and why, and whatever.
From experience, I can tell you that the only way you're going to solve this is to try them yourself. We have no way of knowing your level of expertise in the world of computing, so cannot advise properly.
A good way to start is to try out some of the more popular distributions. Good examples are FC4, Suse, Slackware, Mandriva, Debian.
There are good step=by-step guides on this site, and elsewhere on the net. try www.tldp.org