Very nice!
Have you considered using S/H mode to use shadowed background tiles? That'd basically let you have a twice better color depth. You'd be limited to darker colors for background tiles, but since such games are generally dark, I think that's a good fit. Sprites could still use non-shadowed colors, to stand out.