I can apply that to pretty much every game ever. "Contra's not hard if I memorize all the bullet patterns" etc. Granted action games have that added pressure of input like you mentioned, but for a purely turn-based game that's probably not going to be there.metagame.
The problem with that statement is that Contra is still hard even once you know the bullet patterns.
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.
Applying this back to action games, just since I'm on a shmup kick lately, I think there's also an element of having to keep multiple /things/ in mind at the same time -- although this might just be another way of saying "thinking more than one move ahead."
Mars Matrix is really cool about this. You have some enemies that fire off fixed patterns of bullets, and some that fire aimed attacks -- I think most are aimed -- so this leads to bullet patterns interacting in a less predictable way based on where YOU are when the attacks go off.
Second, enemies drop cubes when they die, and you can pick them up for points and experience, which results in weapon upgrades. And if you want to maximize your bonuses you need to pick up additional cubes before the chain meter runs down, forcing you to take risks if you want to maximize gains.
Finally, you have two main attacks at your disposal, as well as a shield/smart bomb. The shield has a recharge time based on how long you used it previously, and it sets off a smart bomb if you deplete it fully, so you have to balance all this stuff out.
What it results in is a game where you have to pay a lot of attention to what you're doing and plan ahead if you want to control what the enemy bullets are doing.
Going back to the strict idea of thinking more than one move ahead, though, well design fighting games are /heavily/ based around this. I saw an article about Virtua Fighter 4 that was talking about this, and I wish I could find it, but basically it was talking about how many levels of attacks you need to think ahead to be able to effectively counter your opponent and trick them into giving you an opening.
If you throw a high punch, they can get a low kick in -- both you and your opponent know this. So obviously you want to use the high punch as a feint and cancel into something that'll interrupt their low kick -- but you could either block or do some downward attack on them, and that you'll do one of them is obvious, but not necessarily which, so they're going to try to do something to deal with BOTH of those, and it just keeps going on and more branches keep piling up, and it's not sufficient to think of just one move ahead because you're easier to predict that way, but it's impossible to think of ALL the outcomes, and some of it gets kind of circular, and so on.
In RPGs it really is pretty much sufficient just to think at most one move ahead. Even in Atlus' games, you can play a very reactionary game without much forethought.
I think the problem is that there's just not a lot of stuff to /set up/ before hand -- you don't really have the tools to come up with a farther reaching strategy because you don't have a lot of variables to deal with.