The main difference I see between real strategy games and RPG "puzzle boss" type encounters is that a real strategy game requires you to think more than one move ahead. You don't need to only consider the immediate situation but also how you're going to be setting yourself up in the future. "Puzzle bosses" don't really demand that. You just need to know that when the boss does X you need to do Y and that's it.
So how do you do that in an RPG? For one thing you could have meaningful buffs/debuffs/status ailments. You could also experiment with variable cool down times for different moves so for example a big attack might leave you vulnerable for a length of time so you actually have to think about when to use it. And for the love of god make healing actually take some effort. Make it take time instead of being able to restore the entire party from 1 HP to full health with a single spell. A corollary to this is that bosses shouldn't have attacks that take the entire party from full health to one 1HP in one unavoidable hit unless you just want the game to become an exercise in frustration. And in general resources should be limited so you have to be careful about when to use them. The biggest problem I see with most RPGs is when there are little to no consequences for just spamming your best attack all of the time. If there are no consequences for that then there's no reason to do anything else and of course there's no strategy. The end result is just a contest of numbers.
But moving away from RPGs for a second, if you're claiming that turn-based games in general can't do better than "puzzle boss" type challenges then as a fan of turn-based strategy games in addition to RPGs I think you're friggin crazy. The real question that we should be asking is why are so many RPGs lacking the elements needed to offer strategic challenges. Why do they need to resort to petty "puzzle boss" type tricks in the first place?
With strategy games, it's a lot easier to introduce complexity because you've already added something really important that's within the control of the player, which is movement range and distance, and I was sorta excluding strategy games when I made my earlier posts. Scaling back how effective player movement are is certainly one way to do it, but I think the only difference there is that you'll go "I better cast regen at 70%" instead of "i better cast cure at 10%". Either way once you figure out what the boss is doing you can either account for every (or most) contingency (if it's a random rolling boss) or whatever preset strategy (if it's a puzzle boss). I think just by the nature of how a typical turn-based RPG works once you figure out what a boss does you can't fight it again without it being really easy. One way to toss more into this is to either encourage the player to figure out new ways to beat the boss (through a class system or lots and lots of skills).
I think a question is, "why do other genres not need to program as complex bosses to give a fight that can be different/exciting each time?" In addition to the aforementioned having no time pressure (twitching etc), the player's input will have no difference each time in an RPG either, unless we're talking about miss rates- I suppose that could be one way to do it, make it so that there's a chance that cures etc have a chance to either fail or be less effective, but usually when you throw in random chance like that t ends up being frustrating, especially if the game is punishing (ie "lol you lost, redo a 2-hour dungeon"). I guess another way would be to just somehow add time pressure on a turn-based battle system, like tournament chess (or active ATB).
There's also what I said before, introducing human opponents, who are unpredictable. Just too bad AI's definitely nowhere near that sophisticated yet.
I agree with the notion of doing something to fix status effect spells. Namely, by getting rid of those "high-tier" status effects like Death, Break, Stop, and Frog/Pig/Mini
I don't think they need to remove those, I think what they should do is just allow you access to the Bestiary at all times during battle (or make it an ability to punish those with a bad memory I guess?), but you will not get info in the Bestiary until you use a scanning ability or spell. I recently played FFIV TCC and Scan just plain didn't work on a bunch of bosses, which just confused me since that's the whole damn point of the spell.
Aeolus, I don't feel that any of the changes you suggested are really addressing the core problem, namely the lack of depth and complexity. Maybe the changes you suggest make more logical sense, but I don't see them fundamentally changing the way the game is played.
Let me give an example of the sort of thing I was thinking of. Status effects don't necessarily have to be big things. Let's imagine introducing a 'stunned' status. Certain big attacks could have a chance of leaving an enemy stunned for a short period of time and as a result they could be more vulnerable to a follow-up attack. But this is still being done with an attack so you don't feel like it's a complete waste even if the status doesn't take. Anyway, a stunned enemy should take more damage from another attack and probably lose the chance to dodge it. This introduces the opportunity to make types of attacks that are particularly effective against stunned enemies, for instance another character could have an attack that does a lot of damage but has a low hit chance normally. It might not be a good attack to use against an able-bodied enemy but if you get the chance to use it against somebody who has already been stunned then suddenly it seems like a great thing to do.
Now let's add another wrinkle. I said it should take a 'big attack' to cause stun. Well, let's make that actually mean something in the game. A big attack should leave the attacker vulnerable for a short period of time. Not as bad as being stunned, but let's say there's a short 'guard down' period because they just make a giant swing with their big hammer or whatever and can't readily defend themselves. You might want to have yet another character cover them during this period to reduce the chance of being counterattacked. So instead of just whacking the enemies with each character's best attack every turn you have to coordinate the actions of three different characters to maximize their abilities. But the end result should be (if it's balanced right, anyway) more effective than each character acting individually. Now introduce a stamina mechanic or something similar to limit how often these special abilities can be used and you really have to start thinking about when to use them.
And let's talk about magic for a second. Anyone in the process of casting a spell should have a similar 'guard down' status at the very least. Furthermore let's take a page for D&D rules and say that there should be a possibility of interrupting spell casting if the caster takes sufficient damage during the casting period. There's another area where a cover type ability would be genuinely useful, to make sure your casters can actually cast.
None of this really demands dramatic changes in the mechanics of play, but having these abilities that interact with and complement each other dramatically increases the complexity of play. That's what the goal ought to be.
That's pretty much exactly how Grandia works (aside from the stuns being limited), which is one of my favorite battle systems.
I have been too busy/lazy to respond to this thread properly but I wanted to say that I don't think we've seen the pinnacle of turn based gameplay in RPGs, not by a long shot, and that more powerful hardware certainly holds possibilities for combat system growth.
The most obvious would be improved AI.
I can't say I'm super-familiar with gaming technology today, but sadly I'm pretty sure they're still using the same type of tricks they've done with the AI forever. The AI never "thinks", it just does xyz for a given situation. I guess the problem is that there's not even really a demand for "smart" enemies in video games (When the last time you saw a game advertisement go "the computer will respond to you in real time etc"...aside from maybe casual pet simulators, hah).
I also think very seamless transitioning between the game world and combat would be really engaging. This is going to sound dumb, but when I first started reading about Final Fantasy 13, the in-combat screens looked so much like the out of combat screens that I thought it was completely without the usual transition/phasing into combat mode.
I think the sad thing is that MMOs used to be the go-to genre for this and recently they've become less and less like continuous worlds and just become a giant central hub with little instances for people to funnel into. I wouldn't really mind another game that tried it like FF12, though maybe this time they should actually let whoever's making it finish the game.