AVI is not really a video format in itself, it's a
container format for video and audio. The actual file size will mostly depend on the codec you use to encode the video. You can use divx, xvid, or mpg4 for example. mpeg4 gives great quality for the file size, but is still new enough that a lot of older systems don't have the codec installed. Heck, a lot of systems don't even support mpeg2.
But no matter what the codec you use, the final result is a balance between file size and video quality. The quality is mostly determined by the bitrate you encode it in. The higher the bitrate, the higher the quality, but also the larger the file size, naturally.
From your description, I'd say mpeg1 is your best choice, followed by an .avi using divx/xvid. They're the ones likely to be supported by the greatest number of systems (divx and xvid codecs are easily obtainable for systems that don't have it natively). If you play around with the encoded bitrate and frame size, you'll probably be able to find a satisfactory balance of size/quality.
Don't forget the audio codec either. Mp3 audio is probably the best, and if the sound is spoken-word only, the bitrate can be quite small and still be decent. You can even make it mono for even better file savings (though the audio track is generally only a small percentage of the total size anyway).
