Goldeneye and its spiritual sequel Perfect Dark (my favorite game of all time) do this varying AI skill thing along with the mission objectives expanding across difficulties. An argument can be made against it because someone playing on "easy" doesn't really experience the whole game but it's also cool to replay levels on a higher difficulty where the map is larger or you're interacting with more things or you're starting in a different location.

I remember the Command and Conquer games, namely Tiberium Wars and Kane's Wraith. You could set the bot behavior and difficulty. Also, when the difficulty was set to brutal, the bot would have all the limits removed and would start the game with double the money the player had. Even tho this is a rts game, I think it's a good example of how to make bots if devs are given the time and there is an effort for something more.

It depends on the genre of course because of the mechanics in play. Sure, FPS with bots are hard but a lot of genres are as challenging because the mechanics usually surround mostly running and gunning with bots (if you're playing with bots). Making the 'AI better' is going to be extremely difficult, especially when balancing resources out for your minimum requirements.

But for say an 3D action game, enemy ambushes, tougher environmental challenges, harder puzzles, more platforming, increase gear rarity for 'normal' gear and stuff can add a real challenge. Bullet sponges seems like the path of least resistance to development time. Especially if the 3D action game is single player.

Counter-strike specifically is a tough one because what other mechanics can be involved in it? In the original CS:S there were actual environmental concerns like you could shoot off boards on the rope bridge denying that path. When it released, the rope bridge was static and was always there. I'd imagine this was due to resources on the physics vs. 31 other players having to have a reasonable sync with the server and their updates.

Battlefield has done this over the years but instead of making it really dynamic it has been fairly static, even if it changes the map, it always does it the same way. Blow up a building in BF:BC2? The walls will always fall the same way and the destruction will always be the same, so it's like a state on or off update for that location for everyone. BF3 which was newer seemed to have even fewer instances where this could happen as just an example but they also doubled the player count. There have been other games that have done more dynamic updates but every engine, fidelity, language, updates/ticks expectations are all different.

Not every genre or game has to be focused on just your targets. The more mechanics that are offered or can be offered are going to be different but certainly, it seems like many games still do not take advantage of that even though they could.