I feel like just having more variance in the order of mechanics helps to spice things up; SoS EX being the most recent example.

Adrammelech was another interesting one in that his element combos differ on a fight to fight basis (Though he seems to always do a combo of water + fire/ice + wind/earth/lightning) and fundamentally alter how you execute the primary mechanic in the fight.