One interesting thing from that page is that GIF89a allows interlacing. So it really can be that some combo every eighth line is displayed very early on. Moreover there is a notion of image blocks, so for that particular image taking 64x64 blocks for example you could first encode the fishy portions. Also if you used 16x16 blocks you could have true color, though it would be very large, though there would be some improvement running through gzip over http.