find $DIR -type f | rev | sort | rev | tar -cv -T /dev/stdin -f $OUTPUT.tar
Add a -j or -z or any other compressor you want.
This will sort the files on reverse filename order so that similar sounding files will go together. It's not perfect and I had an idea to write something better but since it's usually enough I didn't really bother.
Only thing that is needed is a program that takes a list of files and sets them in order for tar to do the packing and gzip/bzip2 compress the hell out of the pre-ordered files.