Yeah, a simple synth with midi processing would be the way to go. I would greatly suggest again those articles about kb's 64k synth. Aside from targeting the synth to be small (which I assume isn't one of your biggest worries right now), he talks about how the sound is designed, midi data, things like that. After reading those, decide what kinds of sound generators you'd like (simple analog-style ones should surely suffice with proper amp/pitch envelopes and filtering) and hit up musicdsp.org as hellfire mentioned. Great signal processing algorithms there.
[EDIT] - Articles 3 and 4 are focused more on the synth design; the first is more introductory and the second is about using midi data because it's small.