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.
http://git.annexia.org/?p=pxzcat.git;a=summary
I also wrote a random access program for xz files:
https://github.com/libguestfs/nbdkit
(in the plugins/xz subdirectory)
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.