Before I got into "real" programming, I loved screwing around in GM8 Lite. (I'd be lucky if I ever got something worth noting done though...)
Once I began learning Java (After C++; that was a strange transition, especially since I had no idea what OOP was), I began making more complex games. I even made a parody of Minesweeper where you literally have to walk around the map, rather than being able to click and stuff.
Oh, and I made an Asteroids clone for a school project once. ("AAAHHH VECTOR MATH" *Head explodes*)
EDIT: I can't believe I forgot about my procedural terrain generation forays.... They even used cellular automata to make it more believable (via comparing neighbor counts to a random weight function). They made pretty decent-sized maps too (1000*1000 px I think), in about 30 seconds.