This is an excellent search engine for DVD Players
You put in the formats you want it to handle and it displays any that match the criteria. Also if you find a specific DVD Player there may be comments with manipulations of the remote control that may turn the region code to 0. In effect it's the same as paying $150 extra for a "region free" player, except you don't pay the $150 extra.
Also on that videohelp site there's a search engine for converters. One of the easiest to use is DVD Flick. But it's dated now. Another option, instead of converting, is a set top box. If you can spend around $100 there are boxes that can play and upconvert many video formats.
I have always purchased Philips DVD players with divx support. They have some nice features but one limitation that is annoying is that they will only play SD format. If you have an .avi file that's already HD res, it won't play it. You can find yourself in the absurd predicament of downsizing video so it will be accepted by the player which then upconverts it back to HD. Lame!!
I have WD HDTV for USB. It is a bit quirky, but most times if I have to encode a video to get it to play it's just audio encoding and muxing into another container. For example, it won't play DTS audio. So anything with only a DTS audio track I have to convert the audio to AC3 or AAC. There are free tools that work quite well for this. One example is MkvToMP4.
For a DVD Player that can only play the standard DVD video format, then see the software conversion database
Some of the free converters actually produce better quality than paid, unless we are talking expensive professional authoring/video creation suites. Check out the comments on each software for an idea if it will work for you.