Wow, what an open-ended question! I hardly know where to begin...
Let's start with defining how an AI functions:
AI is traditionally state-based; that is to say that the AI takes in its surroundings, and selects an action (aka a 'state') whose parameters best fits the surroundings to do.
Thus, the problem of developing better AI is twofold: a good AI must have a wide variety of states that it can preform, and the environment must be sufficiently expansive enough so that a good variety of surroundings variables can be generated. If either of these is lacking, then the AI won't be terribly interesting.
Let's imagine a great state-based AI entity: it has as many states as I can dream up, each state corresponding to a different set of environmental surroundings. But if the environment is lacking, then this amazing AI can't really do much: put it in a nondescript well-lit hallway without any obstacles or doors, and the only options are either attacking the player or running away. Of course, the AI will still select the most appropriate state (the AI knows that there isn't any cover to hide behind, so it goes prone to reduce its visible 'target area', making it harder for the player to shoot back), but still, the number of options is limited, and so the AI will seem 'bad'.
Similarly, putting an AI with a limited number of states will seem bad as well. It doesn't matter how much cover there is in an environment; if the AI isn't coded to sense the covering objects and take advantage of them, then it'll just stand there and take pot-shots at the player. Boring!
There's a game out there that implements, in a limited context, this concept of (complicated environment + state-based AI with many states). It's called The Sims. =P To sum that game up, there's a complicated environment that the AI's live in, and they will interact with it differently depending on their state: where in the house they are, how tired they are, how clean they are, how bored they are, et cetra. =)
Turn that Sims metaphore into a game: our great AI has values for how wounded it is, how scared it is, how aware of its surroundings, and the amount of time since it has seen an enemy. If the AI sees the player, it will evaluate its surroundings: if there's a good piece of cover nearby, it'll leap for that before opening fire; otherwise, it may drop to the ground and open fire, or immediately take a snap shot off attempting to kill the player before he has a chance to react. If there are an AI squadmates nearby, then the AI will yell a warning so the entire squad can open fire and kill the player with brute force; if the AI is alone, then it might try to hide and then only shoot the player after he has passed.
So, to recap: make the environment complicated, make the AI aware of the environment, give the AI plenty of values to consider, and give the AI plenty of states that it can enter.