Sort files in your tarball by file type, not name. For a moderately mixed case like gnome-games bringing similar files together knocks 3% off the compressed file size (both gzip and bzip2). The trade-off is of course that bouncing randomly between directories is a great way to negate the effectiveness of the directory cache while decompressing.