I goofed with this a bit. It's difficult to compare using more dots vs trying to encode a shape parameter. The image posted above has one image with 6x6 blocks of one color vs one image with 6x6 blocks containing 2 colors and a shape. One simply has more data than the other.
The idea of trading off color data for shape data is interesting. It's what pixel artists already do to deal with jaggies (AA and clean lines). Something like this would store that information directly. Or maybe just process source data with an eye towards removing the jags.
Here is something trying to go the other way. It's a sprite from Ultima IV. The image on the right looks worse, but it also uses less data, so it's hard to compare properly. With 12 extra bits of info available, there could be a third color in each large block, or quite a few more shapes.

Tourist