With scrap parts, I created a Connect Four® style game using an mbed microcontroller, a cellphone LCD, and a few buttons. The circuit itself is rather easy and the Nokia LCD library is readily available online. With the right parts and two hours you can get this running on a breadboard. With a little more time, you can solder it on a RadioShack perfboard. This is a fun project that a novice can attempt. It will give them a greater understanding of serial communication and how LCDs work.
My fascination with gaming devices stems from a game console (mbedGC) some friends and I created last year. The game console connected to a regular TV and this is using a cellphone LCD screen. The LCD used connects with serial and the advantage is when graphics are drawn on the screen they stay there until overwritten. It does not need to be refreshed like a TV does. The mbedGC has to use a framebuffer that stores the pixels it wants to display to the screen and constantly refreshes the TV. This wastes time and memory. The LCD acts like a framebuffer storing the pixels for you.
mbedPG: Make Your Own Portable Game Console - [Link]