In VLC’s preferences, note the setting for “Use GPU accelerated decoding” — on most systems with modern graphics hardware this should be checked, but is not by default. So, check the box and then click Save. You can always change it back if it makes things worse, or causes videos to not play at all.

This setting does not seem to be available in OS X versions of VLC.