É tudo sobre como as configurações de compactação são usadas (ou mal utilizadas, em alguns casos).
O Photoshop é notório por sua saída PNG inchada. O Paint.NET simplesmente aproveita corretamente a compactação incorporada na especificação PNG.
Existe também a possibilidade de outros metadados serem salvos no arquivo, resultando em diferenças de tamanho.
OptiPNG provavelmente poderia tornar qualquer arquivo menor. Na verdade, acho que há um plugin OptiPNG para o Paint.NET. ( Encontrado !)
Some versions of Adobe Photoshop, CorelDRAW and MS Paint provide poor PNG compression effort, further fueling the idea that PNG is larger than GIF. Many graphics programs (such as Apple's Preview software) save PNGs with large amounts of metadata and color-correction data that are generally unnecessary for Web viewing. Unoptimized PNG files from Adobe Fireworks are also notorious for this since they contain options to make the image editable in supported editors. Also CorelDRAW (at least version 11) sometimes produces PNGs which cannot be opened by Internet Explorer (versions 6–8).
Adobe Photoshop's performance on PNG files has improved in the CS Suite when using the Save For Web feature (which also allows explicit PNG/8 use).