So for Cavalry:
First, the vanilla bonus is not weak for $5, it's actually quite strong and probably too strong for $5 even if the card did nothing else. But the vanilla bonus can be changed, so that's not the main thing that worries me about it. The main problem with a one-shot victory card gainer is that you want to put off gaining victory cards as long as possible in general, so you actually prefer having the card in your deck as long as possible before it turns into a victory card, and since it's cheaper, you generally prefer it to the victory card itself. I don't know if that made any sense, so let me exaggerate the idea:
(Card Name)
Action - $5
+$1
You may trash this. If you do, gain a Province.
This card is nearly strictly better than Province, because it's cheaper AND you prefer to have it in your deck (it is better in your deck than Province). I guess what I'm trying to say is that any card, ever, is at least as good as Province, until the very end when you're counting points, and that means that a one-shot Province gainer won't want to do it's thing until the very end.
Okay, so with that being said, your card kind of dodges that issue, but not completely, and it's at least interesting enough that I'm not quite sure how I feel about it. Since you aren't guaranteed to be able to turn it into Province before the end of the game, it's not strictly better than Province. I *think* in most games you would have a decent shot at it (>50%?), but it's really hard to say. You also can't control whether you do or don't trash it when you play it, which also keeps it in check (you may get the Province earlier than you wanted).
Some things I like about it: It encourages engines a little (I think?) by rewarding you for waiting to green. In fact, it even has this cool thing where you can draw your deck most turns, which increases your handsize which decreases your chances of turning this into Province, and then as your engine sputters out and your hand size on average is smaller, this is more likely to turn itself into Province, which is near the end of the game when you want to trash it for Province. I don't know if it would really work out like that though, and if it does consistently then it's probably too much better than Province. I also like that the not knowing whether you will ever be able to get the Province out of it makes it not strictly better than Province, so it makes the mechanic possible (though whether it works in practice you will have to find out through playtesting I think).
So for the vanilla bonus, what you have right now is way too strong. I like that it draws, since that makes it harder to turn into Province. Maybe try just +2 cards, if that's too weak, +3 cards, or +2 cards, +1 buy.
Okay, a thing I just thought of right now before posting is that it's bonkers strong with sifters (Warehouse especially, probably Cellar as well), since those make sure you don't have Provinces in hand. Still I guess it only hits if your opponent has at least one Province in hand so maybe it's okay.
Now my comments on Gallows:
I don't find it particularly exciting, but balance-wise it's probably okay, possibly too weak. It's basically a more expensive Forager that usually gives more money, but with the drawback of letting other players trash a card. That drawback is actually pretty big, but Forager is a very strong $3, and this is otherwise better than Forager (except the drawback). I think the card may not be as interesting as you expect because most of the time (>75%?) both you and your opponents will trash something, and then it's kind of just a +buy silver with all-around thinning for everyone. I would suggest different vanilla bonuses to make it more different from Forager, giving cards (instead of coin is probably best) would do that. Actually now that I think about it I really like +2 cards instead of +$2, that makes them more spammable which means people will thin really quickly (whether they are the ones getting them or not), which means you will actually get the exciting new mechanic to be more interesting since people won't trash as often (after the early game). Maybe then switch them though, so +2 cards if you trash and +1 action, +1 buy if other players trash.