Quais são alguns aplicativos Android que eu posso criar que vão parecer impressionantes no meu portfólio?

Isso depende exclusivamente do tipo de posição a que você está se candidatando. Com base na pergunta sobre o portfólio, acho que você está se candidatando a posições júnior. Ou talvez no nível médio.

Eu entrevistei dezenas de programadores, então eu sempre pedi para que me mostrassem os aplicativos que eles fizeram, mas também para que eu pudesse verificar a estrutura, metodologia, padrões, etc.

A minha sugestão é tornar o projeto disponível no Github para que o entrevistador possa revisar o código. Siga os melhores padrões e práticas para fazê-lo. Não importa o que você faz, desde que pareça que você sabe o que está fazendo. NÃO copie código complexo do StackOverflow ou use coisas que você não entende (como genéricos). Também NÃO pegue algum outro código público e mude-o um pouco. Se um entrevistador for tão experiente quanto eu, ele o lerá em 5min.

Outros caras lhe deram bons conselhos para fazer um aplicativo que resolva um problema. Mas eles esqueceram que isso é a coisa mais difícil de se fazer. Se você codificar um aplicativo que resolve um problema, ele provavelmente terá mais de 100k usuários e ganhará mais do que você ganhará em sua posição alvo :).

Eu faria tal aplicativo que usa tecnologias que são usadas na maioria dos aplicativos como: suporte para todas as telas, notificações push, animações, API get/post, salvar dados em banco de dados, trabalhar com JSON, passar dados entre Atividades e Fragmentos. Com base nessas solicitações, tente fazer um aplicativo por conta própria. Não precisa ser perfeito, mas se o entrevistador vir que você fez isso corretamente, você definitivamente irá para a próxima rodada.

PS. não se esqueça, que as empresas estão procurando por paixão também, não apenas habilidades de codificação ou sede por dinheiro.