I'm a Red Hat fan so I would say go with the fedora. The install is pretty easy too and it supports more hardware than other major linux installs.
I haven't tried gentoo, but I've heard good things about it.
Since you're a linux newbie, going with fedora will be a better decision because you'll be able to find help a lot easier on searches and such.
Good Luck!
