On the Evo I use Rockplayer, and it's pretty much played every format I've thrown at it. The stock player isn't bad, but it won't play as many formats.
I convert my movies/shows from DVD or video source (downloads, etc.) via PQDVD or DVDFab. Neither are free, but they're both like one or two-click solutions, and I got tired of dinking around with multiple apps and processes in order to keep things free. Since I'm trying to save space on the SD card (even though it's a 16GB one), I typically encode with h.264 so it maximizes quality in like half the typical space. I used to not care so much when I was using lesser resolution devices, but the Evo's screen resolution is less forgiving.
If you want a free solution, you can always go with the free version of DVDFab and then convert that output using Handbrake or Super or any other free encoder of choice.