A lot of power cards are not that hard to beat. Some affect you and the AI equally -- it is simply a matter of figuring out how to use them effectively (which may require modifying a deck for that opponent). Others give the AI a slight boost that is usually overcome by a player's superior skill and decks. Some provide the AI a significant advantage, but only for a short time. If you can endure the first few turns (until that advantage times out or naturally dissipates) you do fine. But there are some decks that are almost impossible. Remember, you do not have to defeat every territory of every region to advance to the next level. I simply skipped the territories that were proving too difficult. And I don't think any territory is impossible to defeat -- they generally take carefully planned decks, practice, and a good bit of luck. But they do guarantee you'll always find challenge. After all, how much fun is it to beat up lava imps and albino cave slugs?
Don't get me wrong - I'm enjoying it immensely and certainly do not want a easy walk, as you say where's the fun and sense of achievement in that. However, I do think that it seemed early (particularly considering how far I still have to go) for the AI to be giving itself a leg-up.
Yes, I can see how you might feel that way. But the earlier level decks, whilst some do have Power Cards, tend to use weaker/worse decks. At all of the lower player levels, there are map regions that don't use these cards, so if you really do have problems with one, you can always skip it and pick another region to fight.
Another point is that not all power cards are equal – far from it. So early on you will most likely see the weaker ones, or ones that can actually be used to your advantage with some thought and planning. Later on, they often blatantly add to the AI's strength because by that time you will be a far stronger player anyway and will need the challenge.
Another minor point: a Power Card uses up a slot. You know for a fact that the AI won't be placing an item/aura on that slot, which can sometimes be used to your advantage.
Incidentally, it is more than likely, that in future levels players will get to use Power Cards on their side of the board – you won't ever own, collect or buy them - they will just appear on your side of the board to help you on some levels; the smart player will then have to think of how best to maximise the gain from them.