You can have the good without the bad, but it's more work
While introducing randomness is often the easiest and most effective way to reduce predictability, it is not your only option. You can also
- give players more tactical choices, add complexity in how those choices interact
- model characters in greater detail, allow for emergent properties
- restrict the flow of information, create uncertainty
One big advantage of videogames over pen&paper RPGs is that you're not limited by how many rules and variables players can keep track of or in how much detail you can describe a scene before people get bored or confused. The computer can handle all the calculations, you only need to worry about the presentation. A seemingly straightforward result like "hit or miss", "glancing blow or critical" can depend on a whole host of variables and circumstances, each individually simple to track and understand, but difficult to predict all at once.
I've had this specific problem in a recent project and decided against RNG as it was inappropriate for the (sub)genre I was aiming for. The trick is to look at each interaction (e.g. each action in a fight) individually and ask yourself "how can I make the outcome of this less predictable in a way that adds tactical depth?" Think outside the box. Try to identify popular/effective strategies and think of tweaks to make them "branch off" into multiple different scenarios.
You'll likely come up with a lot of new mechanics, new stats to track etc. That's okay. Don't implement or discount anything yet, make a list. Once that list is nice and long, pick the options that fit your theme and provide the best cost/benefit ratio. Implement a handful, test, reiterate.
Basic suggestions for a "character attacks and does x damage" scenario:
- Instead of dice rolls, make damage scale with stamina (melee fighters), distance to target (marksmen), distance moved this turn (cavalry) ...
- Give units an ability to take reduced damage from one direction/target/damage type/... and allow them to switch between these options
- Add a spell or ability that gets stronger or weaker over time, to mess with target priorities
- Allow units to damage stamina/morale/initiative/... in addition to hp. Make them choose one.
Note that all but one of these suggestions interact in some way with positioning, which you stated should be important in your game. You'll usually get the most mileage out of new mechanis if they tie into existing ones, preferably ones that are central to your game concept.
Use resources to mitigate bad luck
If you do want random damage rolls, one way to keep it "swingy" but reduce frustration is to give players a limited resource that can be used to "defend" against particularly bad results by, say, allowing a re-roll or shrugging off half the damage from a critical hit. You can also tie this resource into a risk/reward mechanism, where running low or not replenishing it means faster progression. Offer risk-averse players a "path of minimal frustration" and let the firebrands have their unmitigated chaos.