Is it possible to tell Mailman to send outgoing mail for a mailing list in several separate batches?

It already does.

My mailer (Exim) delivers a message for multiple recipients sequentially. Of course, this is more efficient in terms of network usage, but processing several batches in parallel is faster (and network bandwidth isn't an issue here).

Oh, do you mean "simultaneous batches"? If your Python is built with threads, you can use mm_cfg's MAX_DELIVERY_THREADS. I've never tried it. As with everything you can set in mm_cfg, see Defaults.py for documentation, and set it in mm_cfg.py if you decide to try it.

In addition, administrative requests are not handled until the cron/qrunner script is run---I'd prefer if they were dealt with immediately.

Yeah; I know Barry's working on redoing some of that stuff for 2.1. Right now, it runs as a queue message, just like all the rest of it. I don't see any good reason that you couldn't invoke "<path-to-python> ~mailman/cron/qrunner" from the mail alias that accepts commands, or from the end of the CGI script that sends commands.