Is it really? If you trash one Province from everyone else, isn't it like gaining one yourself? But it does suck for one player if they lose a Province and the other two don't.
I still think that trashing $5 and $6 cards is more abuseable than trashing Provinces. That case is not comparable to Remodel.
Why would it be less comparable - because of the fact that the attacker is choosing a $3 or $4, and the defender is not choosing which $5 or $6?
When you use Remodel, you are trashing one of your own cards to gain a card for yourself. With this attack, you are trashing one of your own cards to trash one of your opponents cards.
In the case of Gold for Province, the two are comparable.
Legendary Sword: I trash a Gold, you lose a Province. Province is still a junk card, so your deck has one less junk card.
Remodel: I trash a Gold, I gain a Province. Province is a junk card, so my deck has one more junk card (comparable to you having one less junk card).
Note that this doesn't actually tell the whole story. In the case of Tournament, Legendary Sword still stings more because it hurts the opponent's chance of getting any prizes. Then again, you could say that Remodel improves your own chances. So it's still comparable.
In the case of $3s and $4s, you aren't trashing their junk cards. You are trashing their GOOD cards. The earlier case doesn't actually hinder their ability to continue playing their strategy (except for that Tournament caveat), but attacking their Gold and power $5s can stop them dead. So, trashing their Provinces hurts their score but doesn't hurt their tempo. It actually hurts your own tempo, since you have to sacrifice a Gold. But a $3 or $4 card is a much smaller sacrifice (it's easy to pick up extra), so doing this instead can hurt their tempo a lot more.
With Remodel, you are not hurting your opponent's deck. You are just improving your own. The impact on tempo is different. Against Remodel I can still do my own thing and have a fighting chance. But against Legendary Sword, you can destroy my deck and leave me no good way to respond.
I hope that makes sense. Since Legendary Sword isn't a real card, I am just theorizing here.
Legendary Sword 2 seems better. The $4 for $5 case is still a bit worrisome, but less so.