A 3d rubik cube, maybe a 3d tetris (well, 3d tetris has never been fun, but its a challenge to programme).
maybe one of those ball & physics games.... or maybe a hyper-complex-retro-text-rpg with random worlds, random characters, and random..everything. LOL
Random-generated stuff adds a whole new level of complexity to your game.
That would be the dream! I was never that interested in it to be honest - cool concept but does it really compare to some of the mmorpg's/fps's out there? -- OFF TOPIC XD
I like the miniworld + creatures idea. That sounds like an excellent idea.
You could have all these little ants (or something) crawling around. Maybe you could look at the source of "Polyworld" (I think it's written in C or C++) which is an AI program of all these little polygons that move around and eat food. Takes like 4 hours to set up but it's fun when you finally get it working :P
No-one has managed to do it on windows yet though.
How about a Tetris clone? You could spend half your time trying to replicate the algorithm, a quarter trying to replicate the 8-bit soundtrack and another quarter actually programming it.