The minimum expected resolution for a high quality video is 720p. You need to record in 720p or higher resolution. All modern DSLRs, and phones provide the option for this. If you use a phone to record, ensure it has built-in HD camera.
I have an idea for you, try to convert your videos to a different type or extension using online websites, it is for free, and when you convert them there is an option where you can select the quality, try it, it may work.