I think AVI is best suited for a Progressive at best download. AVI is not easy to compress, especially for Web. I think a better strategy for your client is either an MPEG-1 encode or Windows Media with version 7 capability. With those two it will work on almost any running PC out there and both MPEG-1 and WMV will compress much easier than AVI ever will.
I haven't done anything that small in years. All I have to offer is, if the client wants something to
stream at 56k, I hope you're actually making it 48k or so, because most 56k systems are actually 53k (at their best),
and when you take into account the inefficiencies and overhead, you're really talking much less than that.
Now you've got an even worse looking low-resolution video (with lousy audio). My humble suggestion is to educate the client.
If they still really have customers on dial-up, then they shouldn't be trying to stream video to them. It will
look like crap no mattter what you do. A well designed web presentation without video will impress their
clients so much more. If they really need video, then do it as a download, not streaming.
As for your encode question, are you perhaps not adding the size of the audio rate to the video rate to get the total encode rate,
thereby giving you 100kbs rather than 56k?
Sorry, I know most of this isn't what you asked, but it *is* the answer (according to me anyway).