Galera há um tempo venho fazendo uma pesquisa sobre estes dois gerenciadores de pacotes.
Sempre usei apt-get e nunca tive problemas com dependências. Pórem em todos os lugares da minha pesquisa encontrava que o aptitude é melhor , que resolve melhor as dependências , que remove as dependências ao remover os programas ,etc.
Agora vem a minha pergunta...Se o aptitude é melhor , pq a imensa maioria dos usuários ainda usam o apt-get?