Then I requested it from another public IPFS gateway and it took almost 6 minutes for the video to start playing.

One way around this would be to break up the video into smaller pieces. Then instead of retrieving the entire file to start playing you would only need the first piece.