Pure Levels are a relatively boring way to advance a character. Bigger numbers. More treadmill.
Use a variant advancement scheme that ties to the narrative.
Instead of just "gain levels", have the villian unlock power sources of some kind. You do have to spend time practicing those power sources ("leveling them up"), but each power source can grant only a certain number of "levels", and is tied to some specific portion of the character's capabilities.
Suppose you have a game with rune magic. Then power sources could be getting new runes, and you'd level up your skill in each rune as you leveled up. The character has a certain number of capabilities; and what that capability does is determined by what the rune-sentence they use and the levels of the runes in question.
Ik Ro Na Tuk might create a whip of fire that entangles foes, then leaves behind a serpent with a special ability to attack them. Your levels in each of those runes would determine accuracy, damage, serpent toughness, and the serpent's special ability.
(These special moves can be hardcoded with variations; then, which rune sentence is assigned which move could be randomized before the start of each game, so learning rune sentences is part of the game's advancement system.)
Once you have done this, the runes that the villian unlocks are the ones that the hero has an opportunity to learn, at least initially, with two exceptions (the "evil" rune for the villian, and the "good" rune for the hero).
Between the first and second part of the game, the villian automatically "levels up" all runes and uses combinations that you have pre-determined. (The villian gets to know every rune sentence, while the hero only gets the ones you have discovered.)
So now, a weak initial half of the game results in a weaker villian, but also a weaker hero. Possibly really careful choice of runes could result in a villian that is using abilities that the computer isn't good at using, but the player is, or that combine really well with "good" but poorly with the "evil" rune, but it isn't a direct "earn a level, boss is a level tougher"; it is "find a rune, both you and your foe have an extra ability to play with".
If the non-boss foes are mostly the same in the second half, doing well in the first half can make the non-boss parts of the second half easier, while at the same time making the boss harder.