Oh shit, I read "online" and voted for that. Can I change my votes?
Anyway, the toughest A.I. for me is Baraka. I feel like his AI was made for when he didn't do as much damage, and now that they buffed him he's really tough. He just completely mops the floor with some characters! First of all, he's on top of you the whole match. And when you try to create some room he can punish you hard. Every time I jump at him he does the spin or chop chop, everytime I shoot a projectile he charges me. Toughest AI fight for sure. Baraka is just really good if you can anticipate the opponent's moves, and the A.I. cheats to know exactly what you're doing. Those two are a scary combination....
Btw, for some reason Scorpion gives me trouble too. Probably because I'm used to expecting a noob playing him and the computer does everything differently. I keep expecting a teleport and blocking high, and he does takedown or hellfire, etc. etc. I also keep forgetting you can block and punish on reaction offline, which never works as well online. Of course, if you try to expect a computer's move he's gonna do the opposite because he can read your moves. And like Baraka he's good if you can anticipate.