First, there is no reason for anyone to ever be frustrated with this game. It is highly modular and has at least 4 ways to adjust difficulty, all of which are intended to be used if you are struggling.
For starters, play on Easy: 35 health for Gravehold, 12 for each mage, and 10 less than listed for the Nemesis.
Also, you should select your mages and your market cards rather than choosing them randomly. Random markets are intended for experienced players looking for a challenge. It's expected that you will hand select things when you are inexperienced. Choosing things specifically to defeat the nemesis in question is absolutely part of the game as designed.
If you are still REALLY having trouble, then go back and start with the Aeon's End base game. (You didn't say which version you have, but chances are it's newer.) It has the most straightforward nemesis, mages and market cards. All of the other big boxes are designed to challenge players bored with the base game. In particular, War Eternal is very difficult.
If your fiance's is getting frustrated at that point, then honestly, maybe this isn't the game for her.
Actual advanced tactics for people who enjoy the base game include:
- Keeping spells in open breaches until you actually need them
- Buying few gems in general
- Buying several spells as early as possible
- Memorizing your deck (at least for the first few rounds) so that you can hold back cards to buy expensive cards. You DO NOT have to use every card in your hand every round, and having a card from your previous hand can often be useful. Having 5 gems in your second hand is typically easy to arrange.
After you get good at the game, most mages have one or two optimal moves they are almost certainly going to do in the first few rounds, based on their exact details. The most obvious are the ones that are forced to open a breach so they don't get stuck with an unwanted Spark in hand. Others have a III or IV breach that is easily opened for an early advantage. Pretty much everyone can buy an expensive card on their second turn if they really want to. (Crystals are at the top of your deck for a reason.)
Regaining player health, healing Gravehold, and card destruction are NOT required dominant strategies to win this game. Moderately experienced players will not need any of this to win (but will of course use them if available).