You can get legal movies (some awesome, some horrrrrible) at

http://www.publicdomaintorrents.com

They offer a variety of formats. Unfortunately a lot of them are poorly seeded, so if you grab one, please seed as long as you can.

WRT the OP's question: Fastest player is mplayer. If that can't play your vid you're out of luck (save up for the N9x0).