Artificial intelligence isn't the problem. If you look at the notes of Bungie on the original Halo CE, the artificial intelligence actually used to be better. They toned it down because, at a certain level of intelligence, the player stops noticing what the AI is doing. They don't realize that the AI is forming complex strategies beyond whatever piece of cover they're hiding behind. Half Life 2 has some great enemy AI for its time with enemies forming distinct roles, yet people rarely talk about it. Why? Because even the best artificial intelligence cannot hold scrutiny when taken out of its element. It's the classic movie joke of how if you give a robot a logic contradiction, the machine can't handle it; because the logic contradiction is something the robot is not familiar with, its "robot-ness" becomes obvious.
The worst ai can be improved by the level design. Take Super Mario Brothers; a goomba has virtually no AI and just runs forward until it hits an obstacle. However, you don't notice this bad ai because the areas that Goombas are placed in the level generally have them bouncing between pipes or falling off a cliff right after they miss you. You are not given time to think "derp, Goombas are dumb because they just run in one direction", because that one thing they do makes sense in their given situation. People complain all the time about modern shooters having terrible AI, yet they love System Shock 2 and Doom, games that had worse AI. Why? Because the rudimentary AI wasn't given the opportunity to be rudimentary; everything it did was effective. You see a shambling zombie at the end of a hallway; it's probably not the sharpest knife in the drawer, since all it can do is shamble and pathfind and bite you. But, because the hallway is cramped and your only way is through the zombie, the AI is allowed to excel at what it does.
Let's compare two games, Dark souls and Assassin's Creed. In Dark Souls, the artificial intelligence is dumb as a brick; enemies will walk towards you and attack without tactics. In Assassin's Creed... The AI is also as dumb as a brick. However, in Dark Souls, one of the things people enjoy is that normal enemies will not wait for you to kill one of them before fighting you. In Assassin's Creed, the AI is infamous for how it sits back and waits for you to beat up its buddies. The AC example actually uses better AI, because it has the added intelligence of being able to wait for you to beat up its buddies. However, the AI is not working at what it's supposed to be doing (killing you), so it feels worse than Dark Souls's basic "hack at him until dead" design.
There are a lot of ways to manipulate the situation so that an AI seems smarter; level design was already mentioned, and limiting the AI's story role also helps (People expect less intelligent decisions out of a mindless zombie than out of a human civilian).