Download HandBrake from http://handbrake.fr/downloads.php
Install it and use it to convert from AVI to MP4. Select IPOD from the list of options.
Also, for best playback without stutter, reduce the bitrate for video to about 192 – 300. Audio has to be AAC with 128 kbits or less for better performance.
In the H264 tab, adjust the 2 variables as shown below: