The issue happens if you re size the original frame and don’t maintain the ratio. To fix it remove the video and re add it. Then when you go to re size it be sure to hold the control button down. You should get better quality that way. If it’s still not looking that great make sure you’re previewing the content using F9 or by publishing to SCORM and checking in your LMS or ReviewLink.
It sounds like a quality or sizing issue. We use to produce videos at the size of full screen to make sure they’re quality matched the largest possible sharing size. Do you have access to the original files to be able to change the video size to match the full screen which may resolve the issue. Or maybe try reducing the compression or republishing the video to HD but then your file size will be significantly higher.