I second a vote for mplayer, the program which released me from codec hell. Right out of the box, mplayer played almost anything I threw at it. The things it didn't play worked fine after I downloaded a few files and threw them in the program's codec directory. It works flawlessly, and that's on Windows!

Given the amount of time that it takes to convert video (it took me weeks to convert all the video I wanted to take with me to Europe to MPEG4), I'd definitely suggest trying a program that can play the files you want to before converting them to a format that works with the programs you have.