If you haven't really got 3D-acceleration, you should use Xshm. It works like a charm on my laptop.
On the other hand, if you have got some 3d-acceleration, xv might suit you better.
Xshm is the safe bet, i guess. It works great here.
If the video in question resides on a DVD, it might also be a question of enabling DMA on the DVD-drive to get better video playback.