Personally, I swear by Debian for my Linux needs.
It's easy to use and easy to install.
When I wanted to install packages - I would type in a root terminal :
apt-get install package name
Apache
apt-get install apache (see the search to see about installing 1.3x or 2.x)
PHP4
apt-get install php4
PHP-CLI - Command Line Interface to run php scripts via the terminal
apt-get install php4-cli
PHPMyAdmin
apt-get install phpmyadmin
MySQL Server & Client
apt-get install mysql-server
Search
apt-cache search packageName
I.E apt-cache search games will search your apt-resources for the keyword "games" and show you a (sometimes very large) list.
Updating your system is as easy as
apt-get update
apt-get dist-upgrade
There's many many reasons why I would recommend Debian to a new linux user but the ease of installing the software you want and need is just the bait.
Just for the record, I would suggest you install with a 2.6x kernel as opposed to a 2.4x
For an X-server, that is... if you plan to install X for a GUI -
apt-get install x-window-system
If you're installing X - and you are new to linux - you'll want to install "Gnome" as well.
apt-get install gnome
Maybe gnome2? I can't remember, it's been too long since i've installed. apt-cache search it 😛
apt-get install openoffice.org !!! Very nice package.. it's an open source office package developed to rival MS Office I believe.
http://www.debian.org - debians official website
http://www.linuxquestions.org is a great website about all flavors of linux
Hope this hels!