The GBA media player is ok - $25US. But the sound quality is horrible and videos come out quite large. It's nice for cartoons, or recordings of stuff like the daily show.
Play yan micro $75 is better for video nativly handling mp4 and mp3. The original play yan needed a patch to do so and only handled ASF - read:low quality mp4.
The Datel 4GB player has gotten some bad feedback for using moonshell as it's main shell. I have the gba media player cf version 2, and i've ordered the play yan. I'll tell you how much difference there is. Video does look freaking amazing on the ds(lite). lord of the rings, even on the lower quality GBAmp looked amazing, even though it sounded pretty lame.