Вот что придумал, в порядке усложнения:
1) Решатель квадратных уравнений
2) Головоломка (например, ханойские башни)
3) Простой tcp/ip чат
4) Какой-нибудь свой проигрыватель музыки с поиском mp3-файлов на SD-карте
5) Свой навигатор на основе какого-нибудь API (Яндекс-карты, OSM или Google Maps)
По пути разберетесь с UI, с сетью, мультимедиа и навигацией.
