For the sake of accuracy, let's remember that an "AVI" is a wrapper, which mostly works to hide the actual video format. From a quick look at the device from the provided link, it appears to have been designed with Divx video format in mind. Divx commonly uses the AVI wrapper. Typically Divx is also encoded with MP3 or AC3 audio, and that's it.
MP3 @ 192kbps is "transparent" quality to a CD audio, the defacto standard upon which many digital audio compressions are based. And to be honest, 192kbps isn't bad. If you hear diminished quality, that's almost always a statement about the encoding hardware or software, and not an issue with MP3 or that particular bitrate (referring to 192kbps).
Honestly, you should not notice any real quality difference between a good AC3, good MP2 or good MP3. If anything, the wider dynamic range of AC3 can make it harder to hear on portable devices. Inversely, explosions and other loud sounds will be "rip the headphones off" loud. (Or more commonly, you'll quickly discover the point at which your small speakers or headphones will encounter audio distortion.)
For me, the biggest issue is deinterlacing. Are these commercial titles that you're sizing down for portable viewing? Or is this homemade videos that you're re-encoding. (Or course, some of this may be moot anyway, as portable devices have small screens anyway -- even the "big" 12-inch screens are so small that many flaws are hidden.
I would not consider WMV.
I'd use
MainConcept Reference for MP4 (if supported), or I'd simply use VirtualDub for XVID encoding. If you want to go with dummy-friendly software, which has quirks and flaws, something like SUPER is easy to use. But again, not without its flaws.
I generally go from other>DVD, not DVD>other.
There are also a number of Chinese $30-range programs. Most of them are spammers, with crappy quality. One of the few exceptions may be Sothink, who doesn't spam to my knowledge. I won't give my recommendation (yet), but I would suggest looking at
http://www.sothinkmedia.com/video-converter/
I've been asked to look at it, but have been putting it off. So busy. (Sothink makes some nifty web dev programs I've used.)