I don't know how well lzma parallelises, but bzip2 is plenty fast for me with a multi-core version like pbzip2, as measured in wall-time on an otherwise idle system. Different considerations in different environments and all that.
Unfortunately there's no multithreaded option for the standard xz uncompression tools (xzcat, unxz). However I wrote (as a quick hack) a parallel xzcat:
The version of the tools that I have installed (5.1.2alpha in Fedora) do support a -T option for parallel compression which I use regularly.
However, it is true that that same option does not seem to work everywhere. At least, it didn't seem to work a few weeks ago in a different system (Ubuntu). The option is accepted, but does not seem to have any effect.
lzma parallelizes very well! My implementation of parallel xz ( https://github.com/vasi/pixz ) works quite well. There are others as well, including pxz and the alpha version of the standard xz. All these tools produce compressed files that conform to the xz format and can be decompressed by any xz utility.
