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.

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

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

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

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