To improve gzip compression, you want "similar" strings to be close in the list. There are a number of ways to define such a similarity; let me describe a reasonable one that works well in practice. Recall that gzip's block size is 64K. Thus, your data will be split into blocks of 64K bytes and every block will be compressed independently. Tho optimize compression, one would need to minimize the number of distinct k-mers (substrings of size k) in every block. The motivation is that all such substrings will be replaced with an identifier.
While the above problem is hard in theory (it is a variant of hypergraph partitioning), there exist fast practical algorithms. I would recommend LSH-like clustering that can be implemented with a single pass over your data. Notice that (alphabetically) sorting is another way to "cluster" similar strings together. However, specialized clustering algorithms can perform better.
An alternative is to use zstd, which is (i) faster, (ii) obtains higher compression ratios, and (iii) does not have limitations on the block size (and thus, compresses strings equally well irrespective of input ordering).