I submit that Legionary is a weaker attack than Militia. Militia always works, even in a one-card hand. You could get Tortured twice, discard both times and still Militia your opponent just for spite. It may not be the best move, but it's possible. You can always open Militia, and it slows down the early game, often making it painfully slow to get to $5
Legionary, on the other hand, is actually its own counter. Since you have to pair Legionary with a Gold in-hand, it only really works reliably if there are engine parts in the kingdom for drawing, sifting and otherwise controlling your hand. If such engine parts exist, that significantly mitigates Legionary's attack, since victims can keep Village/Draw/whatever and still have a good chance of kicking off.
And to make matters worse, having played a few games against it in just such a kingdom with engine parts available, I can say that it does suffer from Margrave Syndrome. I have been saved from a dud hand many, many times by the play of a Legionary. This doesn't happen with Militia.
I'm not saying it's bad. Like many discard attacks, it's often game-defining and it's rarely skippable. However, on a board without engine parts, I would hesitate to try Legionary/BM, and on a board with engine parts, and with both Militia and Legionary available, I would sooner open Militia and have just a single Militia in my engine rather than waiting to hit $5 and using a Legionary for the discard attack.