More stealthy climbing like having to climb a wall jump to the wall behind you climb up that wall get to the top collect *SUPER SECRET NINJA STUFF* Then use a rope like a flying fox to get to the ground again. Have super cool building levels where the whole time you have to climb buildings and jump from building to building, like in some village, im imagining climbing across ropes that hold up washing between buildings. With the killing of three Emperors you'll need to brake into three Emporer fortresses or castles, and to completing this task fully stealthy you need to climb a number of sentry towers and assasanate the look-outs without them setting off some alarm. So for each Emporer there should be a Breaking into fortress stage, a sneaking around Emporers Soldier Camp, Getting pass guards, and then the actual killing of the king/emporer. OH! and another thing you should defiently have cut-scenes at important times, like when you meet the emporers...
Galazor
You could also make a spin off game, maybe Samurai Rampage, where it cold be more combat oriented (more combos and an hp bar). THAT or make a samurai a semi-boss and/or unlockable character.