MP4 is a very common format these days, so you shouldn't have to convert them just to view them. A media player that cannot play them is, in my view, deficient. But this can be fixed.
On thing you can do is download a codec that allows Windows Media Player to play mp4 files. You can get more information about how to do that here:
http://support.microsoft.com/kb/316992#34Another (probably easier) thing you can do is to get another media player that can play more filetypes by default. Some common recommendations for this are Winamp, VLC, and Media Player Classic.
If worse comes to worse, and you have to convert the format of the video, I usually use a tool called ffmpeg, which is quite versatile, but only runs on the command line, so if you're unfamiliar with the Command Prompt it could be difficult to use. I think there's a graphical interface version of it somewhere but I don't know a whole lot.
Anyway, I hope that was of some help.