That's pretty well par for the course for Android, at least version 1.6 we're using on the eDGe. The problem with MP4 is there's effectively a lot of variation with respect to resolution and bit rate. The eDGe seems to have problems handling 720p and 1080p, but work just great with 480p.
Try converting the video targetting the iPod - one user reported consistently good results doing that.
Also, others might suggest doing the playback with the screen rotated 90 degrees (i.e., landscape).
My own experiments with MP4's suggest that the resolution/bit rate seems to be more of the key.