> I was on wireless
If the connection was not extremely bad, 25 MB should not be a problem... And the video should start playing after a few MB have been loaded.
Have you checked that the videos were encoded with web-compatible settings? There are different variants of the content of a mp4 file, and some variant may require the player to load the whole file before it can start playing...
If you work with Chrome or Firefox, please open the developer tools, and have a look in the "network" tab so get additional information on the timing.