tarballs also have to contain libraries that are needed by the game, where the .deb installation files only need to contain the game and a list of the dependencies in order for apt to satisfy them. so that is another reason for their greater size.

Except that GOG doesn't package dependencies in tarballs as far as I know, it's a complete clone of the deb otherwise.

gzip has a large advantage in terms of decompression time. Somewhere around factor ~3 compared to lzma & co, if I recall correctly.
Though I personally would prefer smaller files as well, especially for those huge games like the witcher.
Memory usage isn't really an issue i think. Unless you are playing on a real retro-DOS PC with 32mb ram.

Parallelized decompression helps a lot in case of lzma. I.e. using 4 or even 8 threads boosts it quite a bit. Recently xz supposedly released multithreaded compression and decompression (I didn't test it yet though).

Also, if we are talking about some major games of the size of Witcher 2 and bigger, RAM shouldn't be a concern. You wouldn't play them on low end computers anyway. And better compression matters much more for such massive games precisely. For small games the difference is negligible.

there is also pigz - a multihreaded implementation of gzip ;)
and pbzip2 - a multithreaded rewrite of bzip2
though I have to admit I never closely looked at those.

and 7zip should support multiple cores as well.

anyone up for some benchmarking? :p

I’ve done some quick comparison between gzip & xz there:
https://www.gog.com/forum/general/linux_support_on_gog/post1668

You can see from w221's results that parallelized xz is pretty good, so there is no reason not to use it while at the same time gaining major size reduction.