There are pretty much only 2 factors when it comes to download speed.
Your own maximum throughput and the maximum throughput of the other person involved in the transfer (and technically the maximum throughput of every single network device on the path between the two points).
So if your users generally are connected with bad speeds, decrease the file size, there is nothing else you can do to improve speeds. A decrease in file size will result in lower quality output. There is no magic involved.
If your server is connected to a line with horrible speed, move it to another hosting service that provides better speed. Or better yet, move to a Content Delivery Network.
If all of that is not acceptable, just upload to YouTube and embed it. They will convert your Video into several formats with several resolutions and offer the optimal solution to your client. No matter if they're on horrible mobile or satellite hookup.