Acho que emacs23-nox é o pacote certo para você.
Existe, nos repositórios "regulares" do Debian / Ubuntu, um pacote para emacs sem suporte a GTK? Eu estou em um servidor e gostaria de instalar apenas a versão do console, sem uma dúzia de bibliotecas gráficas desnecessárias.