The built-in media player seems to be at an advantage at the moment as it uses HW acceleration for certain formats - namely mp4, wmv9, avc (aka m4v) and h264.

For example the shipped demo trailer for '9' is a .mp4 (MPEG4 + AAC audio) with a full 800x480 resolution at a whopping ~4000kbps rate and unless you have some background tasks running it's pretty smooth.

If disk space is an issue, that would probably mean going for h264, but more serious measurements would be be needed to tell exactly how much juice can you save by going with a lower bitrate.