First, encode the video to Mpeg4 H.264 because:
- With the recent release of HTML 5 your browser will play them without flash
- H.264 provides a great format for compressing video
- Handbrake has a pretty comprehensive set of settings to create H.264
Read the other comments about a suggested bitrate for small file size vs quality.
If that doesn't work, you probably don't have enough upstream bandwidth to effectively stream videos. IE, your internet connection is too slow.
The solution would be to:
- get more bandwidth
- host the files somewhere else
- share the files using bittorrent
Update
Here's the nitty gritty on HTML5 video from Wikipedia
The current HTML5 draft specification does not specify which video formats browsers should support in the video tag. User agents are free to support any video formats they feel are appropriate...
H.264/MPEG-4 AVC is widely used, and has good speed, compression, hardware decoders, and video quality, but is covered by patents.[11] Except in particular cases, users of H.264 have to pay licensing fees to the MPEG LA, a group of patent-holders including Microsoft and Apple.[12] As a result, it has not been considered as a required default codec.
Google's acquisition of On2 resulted in the WebM Project, a royalty-free, open source release of VP8, in a Matroska container with Vorbis audio. It is supported by Google Chrome, Opera Browser and Mozilla Firefox.