Disk-space permitting, definitely both. You can later decide if you prefer KDE, GNOME or another desktop, but whatever your choice, you definitely want both the KDE and the GNOME libraries installed. Once you have the libraries installed, KDE programs can be run under GNOME and vice versa, which is great because there are nice applications written using either library. As far as the amount of disk space is concerned, the "desktop" is only a small part of the KDE and GNOME systems so you don't save much space by omitting the desktop and trying to install "libraries only". Both GNOME and KDE come with a set of nice programs and tools, so it is definitely worth it to install both desktops in full. I never heard that the two adversely interfered with each other. For every-day work, I use the KDE desktop, because it feels more solid than GNOME. If you like more "cutting edge" and "cooler", go GNOME, but don't complain if things don't always work quite that well.
I would also install the other "alternative windows managers". They hardly take any space (some are really tiny) yet they can be useful under some circumstances. You can run any KDE or GNOME application from under any of them, as long as KDE and GNOME libraries are installed.
KDE is more power hungry. On older hardware (e.g., 133 MHz Pentium) I prefer GNOME to KDE. Other windows managers are ligther than either KDE or GNOME. Therefore, on really modest hardware, I would choose one of the "alternative" windows managers.[an error occurred while processing this directive]