You should look at using MPEG-4. There are two different types of MPEG-4 video formats: Portable and AVC (Advanced Video Codec). Portable MPEG-4is the very small (and very lossy) format that is mostly used with iPods. AVC MPEG-4 is a very efficent format that generates small files and reasonable picture quality. Many players have problems playing AVC, however, as it is still a relatively new format.
If you still want to maintain the HD quality, take a look at AVC-HD (if Adobe Premiere Supports it). This format is also AVC-based, so you might run into compatibility issues.
