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.