I'm not sure exactly what causes this, but I have the same problem with my wife's phone, and my own. I have the Galaxy S4, and she has an iPhone 5C. No matter who we send videos too, they always downgrade the quality.
The only solution that I have come up with is to upload them to Dropbox, and then share the video through that.