Less burdensome? Try openbox.
KDE and Gnome are not window managers themselves; they contain a window manager (metacity for Gnome, and I forget what KDE uses). You can replace it, but I forget how. Google knows. Openbox might be a nice solution to try.
"Weirdly, though, many programs which were not listed in the KDE menus are listed in the ICEwm menus. Now why would a program be installed and not listed in the menus?"
Because it isn't Windows or Mac OS X, and each DE and WM has its own menu system. Some of them try to share some info with each other, but they all maintain separate lists.
"Also, I found that I cannot uninstall Firefox despite it's being a supposed 'third party' application. When I try I get a bunch of dependency warning about X11 -- So apparently I'd damage or disable X11 by removing it. This smacks of Microsoft tactics. Why would they put something essential to the windowing system into an application library?"
They don't, and you can successfully remove FF without damaging X11 (X11 and Gecko have nothing to do with each other, unlike IE and Explorer's window managing bits). The most likely explanation is that the package manager is erroneously detecting some X-related libraries as no longer being dependencies of anything, and thus marking them as safe for removal. Its most likely a bug/configuration error in the package manager.