[Disclaimer: I'm merely a KDE user, hardly involved with the KDE development processes; my criticism is based on what I see as a user, I'll be glad to be corrected in the comments]

Back when I started my way with Linux with the brand new RedHat 6.0 (which as always, preferred GNOME). KDE always went forward: KDE1 was pretty.. basic, KDE2 was a big step, and same goes from KDE3. I've been using KDE 3.5.x for quite a long while (RHEL/CentOS5 and Debian sid until recently). 3.5.x symbolizes, in my opinion, the last "winning' era of KDE:  It had the right features, but more important: it was mature and stable.

KDE 4 introduced important improvements:

• User interface continued the tradition of being much nicer than its predecessors. Compare for yourselves: KDE 1 2 3 4
• Very nice OpenGL effects were added with two important advantages over GNOME+ Compiz: the OpenGL features are fully integrated inside KDE, configuration is way easier (Compiz configuration tool is scary), and the attitude is more towards productivity and less toward eye-candiness. For example, instead of the useless wobbling windows and water effects of Compiz, KDE provides the useful feature that displays all open windows and allows search-as-you-type for choosing the right application by its name, by simply putting the mouse pointer  on the top-left corner.
• Simplified user interface: the developers had the courage to do some rewrites and strip complicated GUIs, even lose some features, and make the new KDE 4 apps more simple. This is mostly notable in konsole and amarok.

But, it also got worse than its predecessors on some areas:

• Relatively instability and immaturity: i've been finding too many elementary bugs, such as closing the laptop lid when locked doesn't send computer to sleep, or low battery warning increases screen brightness instead of decreasing (My examples are especially in the power management area, but not only). Being important yet unresolved for almost a year, makes it really frustrating. which leads me to the next point...
• Relatively inactive community, bad bugzilla state: the KDE bugzilla is too messy: lots & lots of bugs stuck, neglected, on UNCONFIRMED, many bugs that are open for years (even bugs from KDE2). There should be much stricter policy there, irrelevant bugs should be rejected, confirmed bug should be set to NEW for distinguishing real from imaginary, and relevant bugs should be addressed. I'm aware that it's a (mostly?) voluntary project, but it doesn't mean that its problems shouldn't be discussed.
• Unattractiveness to debug and fix the problems by myself: I admit that I didn't try hard enough, but reading and fixing KDE's code is an activity that I'm quite scared of. Maybe its the massiveness of the code, maybe it's because KDE is not yet another application but my desktop environment.

3 things I recommend to the KDE project:

• Focus on stability, start a real feature freeze for the 4.x tree, clean the bugzilla: by either rejecting or fixing bugs.
• Attract more users to become developers and QA guys.
• Elect a leader. As far as I understand the KDE project doesn't have a single leader. This is quite puzzling. I believe that in order to achieve real goals, there ought to be a single person to dictate the direction of the project.

As a new GNOME user, and for being fair, 3 things that GNOME should learn from KDE:

• gnome-terminal lacks many important features that konsole suggests: search buffer, unlimited buffer, notify on [in]activity.
• GNOME's Run dialog (alt+f2) is quite "dumb" compared to KDE's krunner.
• Compiz should be more integrated in GNOME, be simpler to configure and more productive.

I thank for the KDE developers and the Debian-KDE guys for their efforts; I hope to start a real discussion about the KDE project's weaknesses, in order to improve them significantly, so I could switch back to KDE at 4.5.x !