Only for a matter of accuracy... GNOME and KDE are not window manager. They are desktops. Which means that they include a window manager (K window manager or ICEWM for KDE, and any window manager for GNOME, as you can change it), a desktop, a panel and a framework to build apps that have similar GUIs.
RedHat and Mandrake do have both of them. However, my experience with red hat's GNOME has been far better than Mandrake's. And KDE has been far better on Mandrake. So you could base your distro choice on the desktop you prefer (hard to tell before I know).
Anyway, there are several pros and cons to both distro.
RedHat package management sucks. There's no dependencies resolution, so if program X requires program Y, you'll have to find a rpm of program Y to make X install, and then, program Y might have another dependancies, which can make a dependancy hell, as it's often called. But (yes, there has to be a but) if you can live with all the packages included, or don't mind working a bit to make a program install, RedHat is your best bet, as it's the defacto standard. If there are rpms out there, you can bet they'll work on RH (Ximian desktop 2 (which is GNOME with several improvements) has an example, which comes only for RH and SuSE).
Mandrake however is really awesome when it comes to package management. With its tool, urpmi, if you install a program, it will automaticly download all the other program it needs to make it work. That makes the user life a lot easier. The configuration tools are great too, you won't have much config to do, since most of the time, everything works out of the box. The main problem of Mandrake is that it's not as standard as RH, so you might have problems to find packages, but that's a minor problem. But some software are simply not ported (in binary form) to Mandrake (again, I take Ximian desktop 2 as an example).
As for the favorite desktop, personally I prefer GNOME, but I think KDE is more user-friendly at the moment. I started off with GNOME in RedHat, and although it was nice and all, I think I would have prefered KDE to begin with. And GNOME is as configurable as KDE, just that it has hidden some of the useless config options from the end-user. They are still configurable, just hidden.
Finally, the games. Wine & Winex let you play some of the windows game. I've never had luck with any civ games using those 2 program though. Civ2 crashed when it asked you to input your leader name, some say Civ3 works, but it has never worked for me. The only that I ever made to work was colonization, and it worked good, although it tended to be a bit unstable. Point is that you'll never get the same gaming experience as windows with windows games. But (hopefully there's a but here too

) there are more games that gets ported to linux. UnrealTournament 2003 had a linux cd and a windows cd in the box. In most case, it takes the form of a client, that lets you play the game with the same files as windows. There are also free alternative, the first that comes to my mind is
freeciv.
So basicly, for a newcomer, I'd say mandrake, with KDE. Have fun
