I spotted this link somewhere (i forget where) yesterday, which gives you a quick run-down on how to convert video's to WMV (windows media video) format to play it on your 360.
I've yet to try it, but by looking at the details, it seems pretty good. I spent a good 6 or so hours converting a bunch of home movies to test them out on the 360 using a program called WinAVI. That was slow. If this is as quick as it suggests, then im laughing!
Check it out here