I took the reduced color depth into consideration. However on second glance it seems like Imagemagick does not compress PNG very efficiently with default settings. After recompressing with zopflipng PNG was easily able to beat bzip2 packed sixels. Results for 256 color 512x512 Lenna:
Sixel + bzip2: 245K
PNG Imagemagick: 467K
PNG Zopfli 10 Iterations: 188K