I think the textures can be made at any size, but if you have scaled down you most likely also need to clean up (unless you have excellent hinting). Like I said, it depends on at which scale you work best with sculpting. When doing larger sprites/textures, I'd rather work big at the design stage, experimenting with scales and proportions things, hue sliding, etc. Usually the cleanup stage is not that much work. It's almost meaningless to start big if you're doing NES style sprites though, or just something small or something with a very limited palette.
Yeah, it's the left one which is indexed, but it takes a while to spot the differences. The missing pixels and larger value jumps are the giveaway. When I saved it I almost thought that I had mis-pasted and I had to check that I indeed had 2 different versions! However, I'm sure a that a less noisy image with more smooth gradients will give worse results. the solution can be to dither a bit with a brush on opacity.
Anyways, I was thinking of trying my hand at some DotT styled Space Quest screens, but the composition aspect is by far the trickiest bit, not the palette stuff...