O apt-get não remove dependências órfãs se você não passar os parâmetros, já o apititude remove por padrão, desde que seja instalado com ele também. Eu sempre uso o aptitude.
O aptitude é uma "evolução" do apt-get, e embos usam por baixo o dpkg.