On the alternate CD there is the option to install a command-line system. What packages (or meta-packages) are installed when I select this option? What is the easiest way to remove all packages except those and their dependencies (possibly using synaptic or the software centre)?
There is information here about how to remove most desktop environments from an Ubuntu installation.
Effectively, that is probably what you want to do: remove all the desktops and X. Once all the desktops are gone, doing a full autoremove should pull all of the dependencies, which should include all of X.