Gentoo is for experts and people who like to recompile the wheel and all its dependencies. However, it is faster. If you're not a novice with Linux I would recommend Gentoo. (although it compiles everything from scratch, which can be annoying).

Ubuntu is a good distro in my opinion. I used it for a while then removed it to explore some other distros. None of them were as good, and I'm reinstalling Ubuntu this weekend. Ubuntu (and any other distro you want, it's just more complex to set up on some) can run Apache/MySQL. It shouldn't be that hard, but I've never done it.

Both are great. I wouldn't recommend Gentoo for new users, but Ubuntu works great for advanced users, as well. Both are going to do MySQL and Apache just fine, though.

If you can't get Gentoo install, I'd pick Ubuntu by process of elimination. After you've cut your teeth some with Ubuntu, maybe you'll be tempted to give Gentoo a try yet again.

I have to second Ubuntu.
First ever distro for me that installed without months of having to constantly tweak things only to end up with a system that still worked only partially.

Only downside is that it takes up a lot of diskspace, the 4GB disk in my laptop is almost full of it.
But then, the same is true for most if not all other distros (and often to greater extents)...

Somewhere I've red that Debian is the rock upon which Ubuntu is built... What does this mean? What are the relationships between Ubuntu and Debian?

It means that the designers of Ubuntu started by building off of (modifying and adding to) the Debian releases.

So it means, that now, there are "Debian-Debian" and "Debian-Ubuntu" distros? Why are they building something diffrent on Debian? Isn't the "Debian-Debian" enough or is it worse in some way?

I can't think of a single distro that has not been built starting with a code base from some other distro. A very popular Linux distro is Slackware, and there are dozens of distros that are based off of this code. The reason for this is simple: why start from scratch when you can start from a tested and proven code base that has most of the features that you like? Ubuntu isn't Debian, only Debian is Debian, but Ubuntu started with a base of Debian code because the creators of Ubuntu liked the core concepts of Debian and wanted to implement those in their distro.

A good analogy for this is Firefox. Firefox wasn't written from scratch; rather, it was started from the code base of Mozilla. Firefox isn't the only software that is based off of Mozilla code; Netscape, Camino, Flock, and other browsers have all been built from a base of Mozilla.

You may think all this sounds odd, but it happens all the time in open-source software development.

Thanks man, couple of new information for me...

So Ubuntu is only based on Debian and it means, that Ubuntu uses some Debians' basic code like kernel fragments. It doesn't mean, that Ubuntu uses also Debian packages and its other parts. Do I understand right?

Actually, the package format that Ubuntu uses is the same as Debian. The Ubuntu team does develop some of their own packages however. You can find more information about the relationship between Debian and Ubuntu here.

The relationship between a distro and that distro's code base are always different. To find out the similarities and differences between different distros, go to that distros website and look around.