3. Creature experience. Ideally, it should be measured not in levels 1/2/3, but in percentages. Let's say, initially, all creatures have 100% experience. The maximum experience level is 300%, and units at this level are three times stronger than "newbies." However, we hire "newbies," right?
So, for example, a hundred centaurs fought, inflicting a certain amount of damage in battle. This damage is converted into experience; the formula for the conversion (a balanced one) needs to be determined through experimentation. The formula is approximately: experience = 100% + (damage amount * pi) / number of creatures. It doesn't matter. We get centaurs with 150% experience. We go to the Castle.
We hire 50 centaurs. The experience of the entire group as a whole is again approximately 100-110%. That is, creatures continue to level up throughout the game. Flexible experience is another component of the game's non-linearity.

4. Buried artifacts. As you know, by gathering information from four obelisks, you can find and unearth the Grail. However, most often, this either doesn't happen or happens at the very end of the game. So, to enhance the adventure aspect, I suggest introducing a system of buried treasures.
On the map, there are two objects: the buried treasure itself – gold, resources, an artifact; and a marker for it. This could be a "small" obelisk, reduced in height. Of course, creating a second puzzle map is too difficult. The small obelisk immediately indicates the location of the buried treasure, immediately showing the open, black-and-white game screen, as happens when all four obelisks are found. Another type of obelisk could be used: one that indicates where the treasure is buried in words. For example, "40 steps to the east, turn there, and 10 steps back." This is even more interesting and easier to implement.

5. Catapult deployment before battle. This isn't even my idea, and it's not for Heroes 3, but for Heroes 5. However, I think it makes sense to make taking castles a little more difficult – after all, they are mighty fortresses, not sandcastles that heroes with an army equal to the castle's garrison rush to besiege.

In short, if the "ballistics" skill is absent, the catapult does not fire for 1 turn before the battle. It "deploys." With the ballistics skill, everything falls into place. At the same time, the skill will become more in demand.