How about a video game using the LCD module and the push buttons?
Or get a SantaCruz VGA module and do something driving a monitor?
Or wire up an a/d module to it and do some kind of data acquisition that reports to the PC via USB. Or PCI. It could monitor temperatures or something like that. Combine this with a power controller and the MAX II device could control a little robot or something like that.
Altera had a Nios II design contest in 2005. this link shows the papers:
http://www.altera.com/literature/dc/lit-design-contest.jsp While Nios II doesn't run in Max II, looking at these may give you an idea.
Good luck!
Gregor