Depending on what player and encoding platform you are using you may be able to use HLS encoding for your videos. HLS stands for HTTP Live Streaming, a protocol developed by Apple for primarily solving this problem (among others).
HLS basically breaks your video file into multiple small files so they can be "pseudo" streamed using a simple Web server. With HLS you can also encode in multiple resolutions and a player might be able to switch to a lower or higher bandwidth.
The only downside is that most of the players use Flash to play HLS encoded content. Check it out in action here: http://www.flashls.org/latest/examples/chromeless/
Here's HLS demo for flowplayer:
http://demos.flowplayer.org/basics/hls.html
And here is a plugin for VideoJS:
https://github.com/videojs/videojs-contrib-hls
To encode in HLS, you can either use ffmpeg for free and upload files to your server:
https://www.ffmpeg.org/ffmpeg-formats.html#hls-1
Or, you can use a cloud-based solution like AWS Transcoder or Brightcove
https://aws.amazon.com/elastictranscoder/