[kaoD]

Conway's Game of Life.

Easily paralellizable, visually attractive, fun to code and use, has a narrow scope but can be improved with goodies (e.g. color for cell age). If you implement realtime interactivity, it forces you to bridge the gap between GPU and CPU world, which is a skill on its own.

[llukas]

There is caching CPU implementation that is very fast and it is not trivial to implement on GPU https://en.wikipedia.org/wiki/Hashlife

Naive implementation should be good problem for start.