A predictive compression engine. Fun and educational to work on, testcases are easy to write (compression followed by uncompression is the identity), lots of existing papers and code, and if you write the center part well, you can accept code drops of specialist agents, taking advantage of their expertise in some situations without allowing them to degrade your aggregate performance in other situations.

Applications: a shell that predicts what the user will type, finding patterns in logfiles, roshambo and similar games, predicting wiggly graphs, Schmidhuber's artificial curiosity, probably other things too.