Well, first thing, if you're still using MP3s, you really need to stop. AAC (usually put in an
MPEG-4 container, and called MP4, or M4A) achieves much better quality with similar bitrates and file sizes. Not sure how much, or if at all, Graal supports it, though. Graal can play Ogg files, so I assume it can also play AAC. It also might depend on the version of WMP on the user's computer, but I have no idea.
And, of course, it depends on the situation. I don't find MIDIs very useful, and file size is getting to be irrelevant. I don't have any statistics to point to, but I believe the majority of Graal users can download a 5-6 MB file in about 10-15 seconds. I can get up to 2 MB/s online, but it depends on the download source (Graal is actually really (really) fast, I can download 100 MB files from RC in about a minute on Era).
Ultimately I think MIDIs are only good for very limited number of things. Now that we're at the point of the internet where things can be downloaded in virtually no time at all, quality is the focus, and MIDIs don't always provide that.