The data is not compressed a 3rd time, and I'm using lighttpd without 
the compression module (the compression module doesn't support 
compression of dynamic content, only static files anyways)

a tcpdump of the stream shows double compression:

HTTP/1.1 200 OK
Expires: Thu, 19 Nov 1981 08:52:00 GMT
Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0
Pragma: no-cache
Content-Type: application/x-gzip
Content-Disposition: attachment; filename="test1.tar.gz"
Content-Encoding: gzip
Vary: Accept-Encoding
Transfer-Encoding: chunked
Date: Wed, 09 May 2012 22:01:17 GMT
Server: lighttpd/1.4.30

fff8
....................X.O..test1.tar...y<.}.?.OI.$d..(E.b.:mHN..b*.c".

compared to the real file:

_KHHOX)O@Ctest1.tar@l}y<T}{?LOIR$dO)(ERbI:mH

If I disable compress in horde config, all is fine, and everything 
works, but all pages are uncompressed, html/js/css/...

The same issue on my apache config, if I disable horde compression, 
and only use the deflate module, I get compression, plus downloads of 
the gzip attachment work properly.

Seems to be this firefox bug, I suppose:
https://bugzilla.mozilla.org/show_bug.cgi?id=610679

As long as content-encoding isn't in use, on gzip'd files, it's not an 
issue, and since mod_deflate isn't compressing already gzip content, 
it works.

Also while looking at a workaround for this, I found that the 
imp/view.php appInit nocompress option isn't used, cause the 
services/download/index.php overrides it.

I added:
'nocompress' => ((Horde_Util::getFormData('actionID') == 
'download_all') || Horde_Util::getFormData('zip') 
||(substr_compare(Horde_Util::getFormData('fn'), 'gz', -2, 2,true) 
==0)),
do services/download/index.php appInit as a simple workaround.

The other workaround would be to completely disable hordes buildin 
compression, and use browser based compression instead, but lighttpd 
currently doesn't support that for php.

Which means it is probably a server-side (i.e. HTTP server issue).  My 
guess is that you have both Horde/PHP configured to gzip data and your 
server configured to gzip data.  So when received by the browser, it 
is actually compressed 3 times - the browser removes one layer and you 
are left with double compression.

This is a config issue however and should be discussed on a mailing 
list instead of the bug tracker.

I agree that it is the browsers job, just can't figure out why though.

I mean, I can't believe all my browsers have the exact same bug, in 
firefox, opera, chrome.

I've had 3 other users confirm this for me. And on two totally 
different horde4 installs.

Hmm, very odd, I don't have this issue with IE 8,9
I do have it with firefox/opera/chrome on ubuntu or windows 7

I can't reproduce either.  Which makes sense - as Jan says, it is the 
*browser's* responsibility to remove one level of compression before 
the data is presented to the user.

Cannot reproduce. Beside that, it's the browser's job to decode 
Content-Encoding before saving the file.

you have to ungzip before you can ungzip then untar the archive.

:/tmp# file test1.tar.gz
test1.tar.gz: gzip compressed data, from Unix

:/tmp# gunzip test1.tar.gz

:/tmp# file test1.tar
test1.tar: gzip compressed data, was "test1.tar", from Unix, last 
modified: Tue May  8 13:33:03 2012

And what's wrong with that?

Receiving an email with a gzip attachment, gets an extra gzip later 
added to it when downloading the file.
I have confirmed this using firefox/opera/chrome browsers, all latest 
stable releases.
I have also confirmed this using normal apache 2.2 config, and with 
lighttpd (no compression enabled on lighttpd)

Response Headers
Cache-Control:no-store, no-cache, must-revalidate, post-check=0, pre-check=0
Connection:Keep-Alive
Content-Disposition:attachment; filename="test1.tar.gz"
Content-Encoding:gzip
Content-Type:application/x-gzip
Date:Tue, 08 May 2012 21:12:22 GMT
Expires:Thu, 19 Nov 1981 08:52:00 GMT
Keep-Alive:timeout=15, max=100
Pragma:no-cache
Server:Apache/2.2.14
Transfer-Encoding:chunked
Vary:Accept-Encoding