My ideas:
1.Stop the odd single-player glitch that 1.23+ has.
2.Fix the memory bugs.
3.Water inhabits layer 4.5 (covered by 1-4, yet not 5-8.)
4.Doubt it's possibility, but since people are suggesting new enemies: Adjust the enemies so they are at least a little smart. (Turtles dodge and bite more often.)

Special almost impossible adds (that would need a new JCS most likely):
1. A "code" event. Enter some sort of C code and specify a sprite (*.png, *.bmp, *.gif)
2. More events per a tile.
3. "Music change" event. The music could get all dark when you enter a cave, and would be cheery diamondus when you exit.