It depends on the compression algorithm that is used and what level of compression is used. The more compressed it is the worse the video quality will be.
Yeah, it's kinda hard to say to because it depends on how good you want the video quality to be and also the audio quality as well. Can't really help you though 'cause I don't really know what video format an iPod accepts.
I typically encode my videos using XviD and X.264.