About space-saving techniques

I know some techniques to save space like color cycling, palette swapping, sprite flipping and mirroring. Are there other tricks among these?

The biggest gains are the from the compression algorithms used. These don't affect the look of the graphics though.

It can save space to use 1bpp sprites. Aka one color plus transparency.

Also, compression is something that goes well beyond graphics. One of the things that occupies the most space in any game is level maps, so it's important to come up with restrictions and compression schemes that take advantage the inherent redundancy of the types of maps you're using. If levels were stored as raw NT/AT data, you'd be lucky to fit 20 screens in an NROM game, but with proper compression you can fit hundreds of screens in the same space.

There are cases where compression does in fact affect the look of the graphics. For example, Super Mario Bros. uses metatile (16x16 pixel unit) compression and mercilessly reuses many of the special-case brick columns used to build World 1-2. This gives its levels a far more grid-based rhythm than, say, any given David Crane game. Likewise for Mega Man games at both the 32x32 pixel and 16x16 pixel scales.

A game that I'm working on for Retrotainment Games uses 16x16-pixel metatiles in one layer of its map compression. We're trying for a grid-hiding art style, but the artist routinely has to go back and make revisions when a single area exceeds the engine's limit of 256 distinct 16x16-pixel metatiles per area. The level map conversion tool can automatically combine similar 8x8-pixel tiles using a tool written by JRoatch, but that doesn't extend to automatically combining similar 16x16-pixel tiles.

I was thinking of using 8x8 tiles to make more flexible graphics but that would be more time-consuming, and take up more space for maps, but I might be wrong.

I think it would depend on how you did it. if your level design has rows/columns with a lot of the same tile repeated over and over, Run Length Encoding could probably save you a ton of space, probably almost as much as if you used 16*16 metatiles as your base unit. If you used a system like Metroid where you build structures out of tiles, and then build rooms out of structures, the structure data could take up a lot more space using 8*8 tiles, but you could mitigate that by reusing the same structures over and over in creative ways.

I think the way you compress your level data really is an outgrowth of how the overall game is designed and how you want your levels to look and flow.