M5Host covered the major differences, so I'll just report my experiences:
CentOS 4 (I use 4.2) is great. It has great stability, quick RPM releases, and is very fast. I use it on all of my new production servers.
Just as a note: If you installed say 4.0 or 4.1, the moment you run up2date, your version will be changed to 4.2 as the up2date contains all of the core updates. So don't bother yourself to download any ISO's other than 4.0 if you choose 4.0.
Another note: On the aspect of 3.0 and 4.0 using different kernel version, the 2.6 kernel has always proven to provide a MUCH faster system in my experiences.