Personally, I'd recommend CentOS (latest Stable release), Apache 2.2, PHP 5.2.9, Mod suPHP (for security, and ease of keeping permissions straight), IonCube Loader for PHP, Mod Security (modsec), and MySQL 5.0.77-Community. Enable other options as you see fit, during install.
That's what's installed on my dedi, along with WHM/cPanel/Fantastico for administering the Domains on it, and it's been great so far.