Eu criei uma solução para mim mesmo:)
dpkg --get-selections | cut -f 1 > /tmp/all
apt-mark showauto > /tmp/auto
diff /tmp/all /tmp/auto | grep '<' | sed 's/.* //'
Isso primeiro gerará uma lista completa "todos" dos pacotes instalados, depois uma lista "auto" dos automaticamente instalados e, finalmente, criará uma lista de diferenças de todos e auto, que é a lista de que preciso.
Alguma sugestão melhor?