.mkv videos are lagging

i just downoaded some videos in mkv format and i played them in vlc and mplayer (a linux media player) and they lagg very terribly so i tried playing them in windows and they still lagged (i tried vlc, mpcplayer, and windows media player) and still no joy how do i get them to stop lagging (if it involves converting them to a different format then i want it to keep its picture quality without getting those ugly pixelated regions)