[oofabz]

Progressive JPEGs are not smaller. They contain the same data, just rearranged. You can losslessly transform a progressive JPEG into a baseline JPEG and vice versa, without recompressing it. The jpegtran tool, included with the standard JPEG library, can do this.

[revertts]

Larger images saved as pjpegs tend to be slightly smaller than a standard jpeg.

http://www.yuiblog.com/blog/2008/12/05/imageopt-4/

[ars]

If you actually try it using the tool you yourself mentioned you'll see that progressive JPEG's are in fact smaller.

[FrankBooth]

Stream compression benefits from locality of data, so the ability to merely rearrange data can be quite beneficial.