Você pode listar os pacotes não instalados diretamente com o aptitude:
aptitude search "!(~i)"
Você também pode usar o formulário mais explícito, mas equivalente:
aptitude search "?not(?installed)"
Se quiser imprimir apenas os nomes dos pacotes, você pode adicionar uma opção de formatação:
aptitude -F "%p" search "?not(?installed)"
Leia a Referência de termos de pesquisa do aptitude , é útil.