Wow, this looks sick! I'd love to try this out!
One solution to the limited program memory could be to make the game playable in chapters. You can use the EEPROM to save data, and when the player reaches the end of a chapter, it's time to flash the next chapter's data. You could even probably save program data by cutting out code that's not used in some chapters but used in other chapters. I think a game like that would be awesome if you commuted-- once you finish a chapter, you flash the Arduboy with the next one for tomorrow! Plus, if SD expansion does come out, the game will already work!
I'm a big fan of the idea of the Arduboy being home to bite-sized game programs. There's so much opportunity for different types of games on it. You could keep an arcade-style game on your Arduboy at all times, to play between calls. When commuting on the bus, you could play the next episode of some game each day. You could even keep a tamagotchi-type game that you just like to check up on periodically! You might even keep one to be used for the HID capabilities, like a configurable gamepad for flash games, or cross computer copy/paste!