Lowest image sizes for computer games

I’m messing around with graphics for an orthographic-view computer game, trying to figure out how I could go as light as possible on visuals to make room for scripting.

The main thing I would like to know is: How are graphic quality (palette size as well as individual color definition, e.g. ‘C89234’ vs ‘DD9933’), processing requirements, and memory requirements all related? What happens when the computer loads a graphic and then displays it?

4-bits/16 colors is what I’ve been working with, but my palette still contains complex hex codes like ‘C89234’, rather than pairs as in ‘DD9933’, and if I switch to the latter type I still end up with pretty much the same file size and a much uglier image. How will this affect performance in the game? I don’t care if this is hardly an issue with modern computers - I want every detail of the game to be as lean as possible!

Surely it isn’t all just about file size - no matter what the palette size is in the image, the computer needs to be able to reference it repeatedly (doesn’t it?), so the simpler the individual colors are, the faster it ought to be able to interpret the code…right?

Any insight would be very helpful!