I'd like to watch the video on my TV as well.
Also, anyone know a good program that does this on a Mac?
on the mac, many people use Handbrake, but you could also use Quicktime Pro and iMovie for example. Basically the MP4 format for Android devices is similar to the MP4 format that can be played on the iPod/iPhone/Apple TV, so I'd suggest to start with that, and work your way up.
For Windows, check some of the links in my signature.