Ahí va mi aporte:
Barcode Scanner (o similares): Para leer códigos de barra códigos QR, etc...
Shazam (o similares): Para reconocer esas cancionar que oímos por casualidad, nos gustan y no sabemos como se llaman
Astro (o similares): Navegador de archivos. Imprescindible en cualquier casos. El otro ejemplo porbablemente sea ES File Explorer.
Traductor google (o similares): Para sacarte de apuros con los idiomas. Algo más diccionario y que está bien es el wordreference, aunque más que una app es un acceso directo a la web.
My data manager (o similares: 3GWatchdog): Para controlar los gastos del 3G (y del wifi, por qué no)
Programa antirobo (cerberus, androidlost, etc...): Sobra explicación. Actualmente ofrecen multitud de servicios y mientras el móvil tenga batería son un seguro de vida. Algunas como androidlost por ejemplo son gratuitas y no tienen excusa.
Luego ya si se les da uso:
Cliente redes sociales: Twitter, facebook, tuenti, blogger. Estos ya son cosa de cada uno así que tal vez mejor no ponerlos.
Edición de texto: Quickoffice (o similares) y/o google docs