They are slower to decode mostly due to decreased cache locality. In sequential JPEGs you read one block worth of data, make pixels out of it, and write the pixels out. In progressive encoding, you need to write the pieces of coefficients back to memory at every scan -- the whole image won't fit into cache -- so there's one more memory roundtrip for every pixel. Also, there's just more symbols to decode in total.