I agree that the skipping has nothing to do with the file size, or format per se.

Since this problem appears at the start of tracks, it might be a gap issue with AAC rather than a 'skip'. AAC files are, AFAIK, not capable of gapless playback unless they are put into an mp4 (aka .m4a) container during encoding.

I don't have an ipod but if I didn't I wouldn't use lossless files with it. The best thing to do would be to learn how to encode gapless AAC files inside an mp4 container.