The best thing to do would be to go into Market and do a search under things such as the file extensions you're wanting to play, etc.
I've looked around and found several players, but don't use them myself and cannot vouch for whether or not they require converting from one format to another.
Perhaps others will post recommendations. In this circumstance, it might not be a bad idea to go ahead and ask in the Android Lounge:
Android Lounge - Android Forums
It seems a bit like a non-device specific query.