It's not 8/16 bit, but I highly recommend
Shinobi Legions(aka Shinobi X) for the Sega Saturn. It's a 2D platformer with digitized sprites, sure, but the thing that makes this game such a gem are the live action cutscenes that look like they were ripped from a Godfrey Ho movie...or a dozen Godfrey Ho movies. You know, classics like Ninja Terminator, The Ninja Force, Cobra vs Ninja, or Project Ninja Daredevils.
The Ninja Warriors(aka The Ninja Warriors Again) on Super Nintendo also comes to mind. It's a sidescrolling beat 'em up with three playable robot ninjas as they tear their way through a military force to stop an evil tyrant: a small fast kunoichi robot, a big hulking ninja robot, and a ninja kamaitachi robot.
For the Genesis, look up another Shinobi game,
Shadow Dancer: The Secret of Shinobi, which allows you to use your ninja dog to maul oncoming enemies. It sticks to the arcade game but adds in bonus levels for extra lives and the like.
Shien's Revenge on the Super Nintendo is a bit different, giving a first person perspective as you fight your way through hordes of other enemy ninjas armed with your trusty kunai. It's best to play this with the SNES mouse.
And then you've got the weird stuff and the other ninja games that are different genres or are more cartoony, like Joe & Mac: Caveman Ninjas, Zool: Ninja of the Nth Dimension, Inindo: Way of the Ninja, Super Ninja Boy, Legend of the Mystical Ninja, etc.