i tried just about every free software there is trying to do this... i don`t know how these .avis are encoded, but mine were either DivX or XviD (one of those...) and it was a total nightmare to get them onto my ipod in watchable quality, and with sound to boot.
it isn`t free, but if none of the free ones work for you, VisualHub is totally worth it. very cheap, very fast and very user-friendly, and includes presets for all of the above (well i`ll get back to you about ps3.. 😛)