Most people will advise installing a decent codec pack. I believe the two best are K-Lite and CCC. But only install one or other, not both. Both would cause conflicts.
Once you install a decent codec pack, most media players should be able to play most files. K-Lite comes with Media Player Classic I think, which is an attempt to recreate an older version of Windows Media Player, before it became so bloated etc. After K-Lite is installed, MPC should play virtually every file you throw at it.
VLC is less hassle, as you don't need to mess with codecs - it has them all built right in. I haven't come across a media file it couldn't play (except those with DRM). Some people say it has poor versions of codecs though, and can struggle with certain content. I have personally never had issues.
The other player I use sometimes is Zoom Player. I have the Pro version, but the free one is almost the same, minus DRM support. It has a tool with it for downloading and updating missing/outdated codecs, to ensure you can play pretty much anything. Slightly nicer UI than VLC.
Haven't tried Plex, but I might have to look into that one. XBMC is pretty nice in terms of eye candy media players.