Take a look at NanoVM (http://www.harbaum.org/till/nanovm/index.shtml). It runs on an 8KB AVR microcontrollers, or tinyvm (http://tinyvm.sourceforge.net/) which runs on the 32KB lego RCX controller (yeah, Lejos is the current version of tinyvm). If you really want to get creative, check out waba (http://waba.sourceforge.net/), I have gotten that down to just under 64KB.
Dan