I agree with your blog post that it's a more interesting assignment than yet-another-Tic-Tac-Toe clone. I wish more curricula did this, and earlier! I think after the assignment is done it'd be worthwhile to show them that they can get all the Java-style OOPy features with just lexical closures, and I think showing Forth as a powerful, simple, and simple-to-implement language would be neat too. (Also yacc and lex deserve a mention, I like this PDF that accomplishes the goal of the assignment: http://www.scribd.com/doc/8669780/Lex-yacc-Tutorial )

If you relaxed the constraint on syntax and just stipulated Turing-completeness, it would be very amusing if someone implemented a clone of Brainfuck. ;) (Especially for the unlucky pair who has to write two programs for it!)