Looks good! Very good choice of a warm "black" too. I've been thinking of making a 3+T colour game myself, and it's always good to see good examples :]

You could probably AA some of the edges. The AA on the tank looks great, and makes the un-AAed parts of it and the tiles look worse by comparison. If you were making a game with only 3+T colours, you'd probably have the "black" serve as the backdrop for the entire game (because what else could be there that wouldn't be distracting?), in which case you'd not have to worry about the AAed parts being seen against anything other than "black".

I didn't notice the characters at first, but I think if the game screen were e.g. GBA- or SNES-sized, they'd be easier to identify since there would be less of the environment to distract from them. Of course, animation/movement would help with that too.
An option to consider: perhaps the characters could use different midtones instead of blue, perhaps depending on their faction. It wouldn't increase the colour count much (the actual assets can even still be 2-bit), but it'd probably make for much better gameplay if you were to make this into a game.

@eishiya: thanks for the feedback, that's a neat idea about the different color character factions. I've tried it out with red and green guys, and they sure pop out more. Will also try to make a simple 2-frame animation for them.

@DB: what would be the solution there? Use middle color as primary somehow? Mute the brightest color to make it less eye-straining?