The other thing Octopath does that absolutely makes bosses harder without feeling unfair is increasing the number of bosses. Without spoiling anything, compare the superbosses you fight alone with the ones that have a party. It's crazy how much even one more enemy affects things.
Another is to play around with expectations. A boss could use stronger skills as she gets weaker, but she could also pseudo counter by adding all damage dealt to her this turn to her attack. Or she can use healing skills only if she took enough damage this turn (which can play well with anti-heal states).
Some general rules of thumb I use;
Could the boss use allies?
Could the allies be "immortal"? Some allies are just different body parts that can be resurrected (which allows you to give the player Death spells without it feeling useless). Another might be an ally that isn't there but helping from afar.
What are the bosses weaknesses and strengths? Push those harder.
Can I turn the boss' weakness into a strength? One boss was immensely weak to magic. I gave it a "reflect" that can be broken down... using magic on it. Another one was not immune to and actually weak to Death... but the first time someone casts the spell the boss preemptively silenced the user with a state that couldn't be removed (but could be immune to and he didn't notice weapons with the side effect, not that you could easily have one yet...)
What is the boss' role or goal in the fight? A boss that wants a slow fight can get counter and increase damage slowly each turn. A boss that's powerful but inexperienced can get "Hyper Beam" from Pokemon, an extremely strong move that stuns the user. A leader can summon more and more allies each turn, leaving it up to the player to keep up or die under the flood.
What is the victory condition? Is it just dropping the enemy to 0HP, or do I have to keep someone alive? Do I have to win in so many turns?
How can I mess with player expectation? Final boss of Chrono Trigger uses the same formula of half the bosses in the game
misleadingly. The beauty is letting the player figure it out.
Am I using all the mechanics of the game to their fullest? I might realize I haven't made a boss around a certain aspect it and push that.
Is the boss a single fight? Many bosses can instead focus on draining resources to make a later (possibly more important) boss fight harder.
Are there any more tricks I can pull out of my sleeve? Any states that a boss hasn't used yet? One of my favorites is in Secret of Mana. There's a boss fight that's honestly very hard no matter what you do... but because you're fighting yourself, it makes the battle significantly easier to just let your teammates die and turn it into a one-on-one fight that you can turn into your favor.
For superbosses specifically, I try to figure out what already exists in the game and I can turn to 11. Is the game based around weaknesses? Let the boss add weaknesses to the party. Is it based around state manipulation? Give the boss a sophisticated AI for playing with states. Do I have bosses that can heal mixed with ways to stop it? Make the boss
drain. The big goal is to make the player feel
puny and get a thrill of beating what feels like a huge deal.
The only two really difficult boss I have to use tricks, ones uses a paralysis effect only curable via an item(ala Red Eyes from Octopath Traveler) and the other mostly uses insta-kill skills.
Generally speaking, people might see those as "cheap" bosses, but both can be built well (Queen Zeal in Chrono Trigger being a good example how to do the latter). Since it sounds like many of your bosses are easy, what is your easiest (but shouldn't be) boss trying to do?
I forgot Red Eye had that gimmick. I, uh, was slightly over-prepared.