Here's... a link to a topic on NESdev: https://forums.nesdev.com/viewtopic.php?f=21&t=16999
The really short version of my post there is that if you have two shared colors in most of the palettes rather than one, you can link in more subtle ways. (If your game is brightish, or cartoony.)
Two games to look at are Kirby's Adventure and Gimmick:
http://vgmaps.com/Atlas/NES/index.htm#Gimmick
http://vgmaps.com/Atlas/NES/index.htm#KirbysAdventure
If your game is dark (like Batman titles) just fade into black and fade back into a different palette.
Granted, I realize it's a bit easier with 256 16x16 tiles rather than 64.