A sequência de comandos a seguir remove o ubuntu-desktop metapackage e, em seguida, todos os pacotes desnecessários e instalados automaticamente (ou seja, nada depende mais deles).
apt-get remove ubuntu-desktop
apt-get autoremove
Se autoremove não fizer nada, então, de alguma forma, todas as dependências de ubuntu-desktop não serão marcadas como "instaladas automaticamente", o que é necessário para autoremove selecioná-las. Você poderia definir esse sinalizador para cada dependência recursiva (manualmente ou com um script), mas não acho que valha a pena o trabalho, se você não tiver problemas relacionados a pacotes de área de trabalho.