Note that Enchantress isn't trying to do something instead of playing though, it's trying to do something instead of following instructions. Maybe I read a clarity into that which isn't actually there, but it seemed clear to me based on the fact that Enchantress states specifically what it is that is being replaced ("instead of following its instructions"), while Citadel only states "instead". The natural English interpretation of "instead" without a "instead of ____" is that it is "instead" of the last verb that was being talked about; in this case playing the card. So I read
"The first time you play an Action card during each of your turns, play it twice instead." as having the exact same English meaning and rules meaning as "The first time you play an Action card during each of your turns, play it twice instead of playing it".
Yes, I know all this, and I was addressing exactly that when I deleted what I wrote because I realized that you were right about the timing because of the intention of the card. I don't agree that the text necessarily must mean that (although it seems to say that); you can also compare with the explanation of Ways in the rulebook. Enchantress doesn't even say "would" although it means that. Which is the only thing I was actually pointing out. In any case, I won't go into more detail, since this is double-moot!
Enchantress couldn't say "would" without other changes as well though... the sentence makes no sense if you just change "play " to "would play". The "would" should proceed "follow its instructions", because that's the thing that you would have been doing which you now aren't. So the whole card has to be
"the first time each other player
plays an Action card would follow the instructions after playing an action card on their turn, they get +1 Card and +1 Action instead [of following its instructions]". The last part in brackets would just be optional and redundant at that point.
In other words, if you are using "would" with "instead", then both of those have to refer to the same action/verb. You can't combine "would play" with "instead of following its instructions".