We are going to be hosting some videos that will be streamed (not progressive download). Which is recommended? CBR (constant bit rate) or VBR (variable bit rate) encoding?
Constant bit rate is intended for streaming media, so that would be the natural choise.
Variable bit rate will give you slightly better quality in relation to file size, but you get much greater variations from the average bit rate. If the average bit rate is close to the capacity of the user's connection, they may experience that the video stops for a while in parts where the bit rate is over the average. So, if the capacity of your user's connection is much higher than the average bitrate that you choose, VBR works better.
I'd stick with constant bitrate
I just had an issue with variable bitrate videos and the audio creeping out of sync with the video.
Flash doesn't know what to do with the vbr metadata, so when it gets a vbr video it plays it, throws no errors, but can give inconsistent results.