Nice effect! I was going to ask how you analyzed image complexity so that the characters had more detail, but you already answered that in that you didn't! There are only two levels of detail. Did you try reducing the palette to say 64 colors so that you end up with a stronger quantized appearance?
You could also turn the Voronoi edges into a bump/normal map and a specular mask so that the tiles pop when the texture is lit by directional lighting. Also, you could come up with different areas of "grout" colors and staining/detail/scratches on some of the "tiles".