Coupla things.
Firstly, you can kill KDE dead with "apt-get remove libqt4". Nobbling GNOME is likewise a matter of zapping GTK.
Secondly, get debfoster and orphaner going NOW.
debfoster presents you with a list of packages that nothing depends on, and asks you if you want to keep them - if you Prune them, all the deps go, too.
orphaner shows you packages that are not depended on by anything - by default, it only shows you libs, but will show you ALL packages that are non-depended-upon if you supply the "-a" switch. orphaner is provided by the "deborphan" package.