We have a similar case with our RTS Remake. All units and houses are sprites. We have 1800018 000 sprites for units and houses and terrain, plus another ~6000~6 000 for team colors (applied as masks). Long-stretched we also have some ~30 000 characters used in fonts.
So the main reason behind atlases are:
- less wasted RAM (in older days when you upload NPOT to GPU it stretched/padded it to POT, I read it's still the same with iOS and some frameworks. You better check on range of hardware you target)
- less texture switches
- faster loading of everything in fewer bigger chunks
What I want to say,did not worked for us:
- paletted textures. The feature existed only in OpenGL 1.x 2.x and even then was mostly dropped by GPU makers. However if you aim at OpenGL+Shaders you can do that in shaders code yourself just fine!
- NPOT textures, we had issues with wrong borders and blurred sprites, which is unacceptable in pixel art. RAM usage was much higher too.
Now we have everything packed in several dozens of 1024x1024 atlases (modern GPUs support even bigger dimensions) and that works just well eating only ~300mb of memory, which is quite fine for a PC game. Some optimizations we had:
- add user option to use RGB5_A1 instead of RGBA8 (checkerboard shadows)
- avoid 8bit Alpha when possible and use RGB5_A1 format
- tightly pack sprites into atlases (see Bin Packing algorithms)
- store and load everything in one chunk from HDD (resource files should be generated offline)
- you might also try hardware compression formats (DXT, S3TC, etc.)
When you seriously consider moving to mobile devices you will worry about constraints. For now just get the game working and attract players! ;)