83k/s is pretty high for 320x240, but not high enough that any half-modern system shouldn't be able to play it if it's got the bandwidth.

The black letterboxing bars are not good for encoding efficiency.. I don't absolutely know that Apple's codec in particular does it, but other MPEG-4 codecs like 3ivx track the motion of 'objects' as they move offscreen, and they can't (don't know how to) do that if "offscreen" is in the middle of the image. Also just representing the sharp line between the video and black takes space. If you really want the black for some reason, since you're using QuickTime anyway you can just add a black 320x240 image centered behind your 320xWhatever actual video. Remember to keep the Whatever a multiple of 8 when you do that.

Apple's codec is not very good either, you could encode with any other Simple Profile encoder and still play with Apple's. I would recommend 3ivx, especially if you're on a Mac. D4.1 will be released quite soon and kicks ass. I have access to seeding builds, if you want to send me your source video I could encode a sample for you to compare. D4 is good too, and there's XviD and DivX 5.

Is there some reason you want to do streaming instead of just progressive downloading? Streaming requires the viewer be able to keep up with 83k/s, whilst progressive download just starts downloading the file and starts playing it when it's received enough to play it continuously. For people with fast connections it's just as good, and people with slow ones they can still watch your file (and save it to disk to watch offline). It's also simpler, just stick your files on your webserver, no Streaming Server required.