That's not true at all. The whole reason why graphics on the original NES were so compact is because the color palette was so limited. Not only that, but tiles could only have a maximum of 4 colors within them, one of which was considered the "transparent" color if you wanted blending. So they were only 2 bits.
So yes, it does absolutely and unequivocally affect the binary size. Having made NES games for fun before, they are two completely different worlds and it's not at all fair to compare them.