Yeah, I will probably go for the Shadow. As Ondeer pointed out, it kinda fulfills two roles for the ninjutsu tempo decks. If I had more space (blue is really tight) I could also see the Thief for some overlap with artifacts.
Nah, I don't think so. Man-o'-War sees play without being incredible...