pbzip2 gives good results and scales nearly linearly. 7za supports atleast two cores at the moment by default, I'm not sure if it uses all cores on quad-core machines. If so, use lzma -2, which will give better compression than bzip2 and which should be faster also.