Can't you just scale down to half-size an interlaced gif/jpeg and have the browser intelligently decide to stop downloading once it is at sufficient quality?