Unconventional response first, but there's a mobile game called War of the Visions: Final Fantasy Brave Exvius, which has a challenging and complex combat system. And the story started getting interesting a few hours in.
However, it is a gacha game. Meaning you get most of the characters from summons, which are usually random.
While you could ignore that portion and get through the story with the characters you get for free, the more difficult content is usually in modes other than the main story mode.
The game is very reminiscent of Final Fantasy Tactics, and has had FFT collaboration events.
For a traditional console game, while I haven't played it myself yet, I've heard good things about 13 Sentinels: Aegis Rim.