Wow, I totally forgot about that. I had tried that once before, but I found it way too complicated. I think there was too much detail to consider
I was thinking something simplier... Picture Street Fighter 2, you're as Ryu, and the bout starts. Each player (Human/CPU) gets a list of moves (Ryu - Walk/Dash Back/Forward, Jump Up/Forward/Backward, L/M/H Punch, L/M/H Kick, L/M/H Fireball, L/M/H Dragon Punch, L/M/H Hurrican Kick). When both moves are entered, it plays the minimum number of frames until one of the players moves expires, where they are allowed to select a new one. So you don't necessarily play your moves at the same time, but it all plays out equally.
I think this way the game would start to favour more that strategist, as you don't have to worry about hitting the quarter circle spot on and throwing out a dragon punch by mistake.
Edit: Here's a quick mockup