This is actually a really good topic. A lot of people have issues getting quality video at a manageable file size.
Here are some of the techniques I use;
The best looking video for web streaming in my opinion is FLV. Unfortunately most of the sites that use FLV have terrible compression settings like youtube, and the videos come out looking nasty. But if you host your own files and use your own compression settings you can get some really nice results.
Adobe Media Encoder does a fantastic job and supports 2 pass variable bit rate compression. this means that the application scans the file once, analyzes where it can get away with higher levels of compression or where it needs to have better quality and then on the second pass it applies those settings, changing the bit rate as needed.
The draw back is that some parts of your video will progressively load very quickly while some places will take a bit longer, if your viewer has a slow connection this can cause a few hiccups. But for a DSL or faster connection you can get great speed and quality.
My typical settings are 900-1200 kbps per second with an audio quality of about 64-128kbps depending on the audio, more complex audio with a supporting soundtrack will need a higher quality like 96 or 128, simple speech can get away with 64.
For directly sharing files I've found that Quicktime seems to be what most people have, DivX or Xvid work great but not a lot of my clients know about them so they don't have the codec installed. Walking them through an installation just to see my video is kind of counter productive when you're supposed to be a multimedia usability expert.

Most people have Quicktime and if it's up to date the H.264 codec is pre-installed.
For Quicktime I use H.264 set to high or in between high and best. Setting it at best seems to make it hard on some computers. Again with the H.264 dialog you can choose 2 pass encoding.
Here's the trick with H.264.
After an H.264 compression your files will lose some of their contrast and it looks kinda crappy which can be frustrating.
If you open the file and go to your A/V controls in Quicktime you can turn up the contrast a little bit and adjust the brightness down if needed till you get the image you want your clients to see.
Then you need to save the file, just a normal save and this will save the A/V settings in the quicktime file so that anyone who opens it gets the file with the contrast and brightness already adjusted.
You can also get really good quality WMV files if you download and use Windows Media Encoder, but I've had a few issues with this application and it's got a somewhat frustrating interface.
Lastly, if I'm uploading to Youtube, Vimeo or something like that I use Quicktime Animation quality or Photo-Jpeg quality and try to get the file as close to the maximum allowed file size that these sites will take.
The reason for this is that public video hosts will compress your file again with their default server compression settings.
If you've already compressed your file the server won't take this into account and will still re-compress your file, compounding the compression quality issues already there and adding new compression artifacts.
The result is a terrible looking file.
With the audio I try to do the same thing 128-256 is the rate I try to stay with and still keep the file in the maximum allowed range.
Unfortunately some of these servers will also ruin your contrast and brightness settings and the video won't look as nice as it could. Really theres nothing you can do about this but hope it comes out ok. Sometimes the luxury of free file hosting has to outweigh the desire to have beautiful videos.
Hope this helps a bit.
