Cool. You are correct that the GBC can set the palette per tile, unlike the NES.
Not sure if you can do palette per scanline tricks on the NES like you can do on the GBC. (I'm more familiar with the GBC hardware)
And you can use layered sprites to get more colors, but due to sprite count limitations that generally isn't super effective. (But Links Awakening DX uses this for Marin's face on a zero death ending, where it has 3 layers to get all the colors in)