The playback is very choppy plus every time I try to rewind the video using the arrow keys on my keyboard, it feels like everything is just slow and there's a noticeable delay between the audio and video tracks. This makes it virtually impossible to watch anything HD. Other files such as MP3s and non-HD-quality videos work just fine.
Before I installed Ubuntu Mate 16.04 LTS on my laptop, I used the Videos video player that ships natively with Ubuntu as its default video player. The same thing was true even there, HD videos wouldn't play in VLC, but when I opened the same HD files in Videos, everything worked fine. I'd really like to use Videos again, but the problem is that Ubuntu Mate does not have Videos listed as an installable package in its Software Boutique.
Do you have an Nvidia card? If that's the case, it's a bug, look here: https://trac.videolan.org/vlc/ticket/16877
As for installing videos, that's called totem.