Какую программу для андроида можно написать?

Вопрос в другом с какой целью вы её хотите написать? для кого? или чтоб заработать? а если с целью заработать даже если она будет крутая то не заработаете. Понадобится много денег на рекламу и раскрутку без рекламы и раскрутки она не принесет денег. А если у вас есть деньги на раскрутку как правило нужно много вложить чтоб потом получать то создайте аналог уже чьего нибудь приложения просто внешне его измените и может немного что то добавьте и куча рекламы и готово.

Написать можно любую программу для Android. Если хотите чтоб она пользовалась популярностью можно использовать два подхода - сделать что-то примитивное (типа часов), но с нестандартным оформлением или функционалом или сделать нужную программу в слабо охваченной области (учебные программы для школьников, энциклопедии, редакторы формул, программы для автоматического повторения действий пользователя и т.п.).