Что создать начинающему Android-программисту?

В первую очередь, все зависит от того, насколько андроид-программист начинающий.

Все может начаться с простого калькулятора, девять кнопок для ввода цифр и простейшие операторы: деление, умножение, сложение, вычитание. Слишком просто? Добавьте возможность выбирать отрицательность/положительность выбранного значения. И это не составило труда? Пожалуй, стоит добавить степени, логарифмы, возможность работать с большими значениями (от 10^10, скажем). Хочется больше реальной практики? Что ж, отрисовка графиков и логарифмы не заставят вас скучать.

Калькуляторы не интересны? Угорайте по сетям и протоколам. Пускай софтина собирает все с вашей почты (POP3 и IMAP библиотеки-парсеры в качестве готовых решений) и выводит в качестве нотисов заголовки и текст письма. Реализация виджетов тоже может быть довольно интересной. 

С сетью тоже скучно? Ладно, давайте парсить содержимое сайтов. Сделайте софтину, которая позволяет смотреть вопросы с TQ по заданным тегам. А что? Тянет на рабочий стартап.

Хотим в математику? Алгоритмы наше все. Не зря же в вышке на парах матана корпели над лекциями, пока бездари-одногруппники играли в hearthstone на айпадах. Пускай софтина вычисляет что-то реальное на основе данных, либо же введенных непосредственным пользователем, либо спарсенным откуда-то (e-maxx.ру/algo/ в помощь). 

Хотим замахнуться на святое святых? Угорим по криптографии. Присобачьте библиотеку для генерации криптостойких псевдослучайных чисел. Напишите на ее основе генератор паролей. Слишком просто? Напишите ее сами.

Короче говоря, делайте что угодно, но делайте так, чтобы она работало и это можно было продавать.