I have an mp4 that's a little over 23 minutes long at about 120 MB in size and dimensions of 633 x 290. When I test the movie on my laptop locally, it starts to play almost immediately as the file progressively downloads in the background. However, when I run the movie on my web site, the entire movie file has to download before the video begins to play.
Any ideas why this would be the case?
That's a pretty large file to wait for a download, most won't. Sounds like you might want to consider a couple things:
Host it on youtube, then embed it on your page.
Use video streaming server software on your host.
Use a streaming service.