Not all games have difficulty modes though. So I guess the question should be is there difficulty settings in this game?
I'm a big fan of the Fallout/JA2 style difficulty (i know, different systems, I'll explain)
In Fallout 1 & 2, the map was fairly constant, so if you go to this area you know you will fight monsters of higher/lower difficulty then in that area. The standard player is lead along your typical "medium" level difficulty, if they struggled they could level grind in newbie-ville a bit. For the hardcore/expert/I wanna be the man style players though they could access incredibly advanced stages with opening characters that allowed them to set their own difficulty.
It was "expert/hardcore" difficulty to beat the game without ever leveling up. It was hardcore difficulty to speed-run the whole game (i.e. go from 1st level to last level and beat the final boss).
And it was a lot of fun to combine the two. So once you knew the game you could skip to the best weapons/armor in the game...then go back to newbie ville and rampage through everything, Hulk style. The players could define their own path which made replayability far more fun then this artificial "let's just throw in collectibles to make it "replayable".
JA2 was nice because there were "options" that you could set to customize the game that also made it more/less difficult. Ignoring their difficulty & save system, I'm referring to their Realistic vs. Sci-Fi mode and Tons of Guns vs. Regular. If you didn't like to worry about ammo management etc. you could select tons of guns and never have to worry about equipment because your dead enemies were a cornicopia of loot. It allowed you to focus on the tactics instead of the micromangement of the game. Meanwhile with Sci-Fi mode, it unlocked certain items and levels that were very difficult, but also had big rewards if you beat them.
Instead of worrying about gimping/boosting the AI to make it more/less competitive for easy/medium/hard, why not have the main path be Medium, allow certain tactics (i.e. w/ strategy guide help) to make the game easier, and have "advanced" paths and challenges for "hard". That way you don't have to play the game 3 times to experience the full gambit, you could experience everything in one playthrough...and then hopefully want to experience it all again in a different order in a different playthrough.
Perhaps conquering your opponents in different order or trying out a different technology path. Trying for a passive conquest instead of full combat 24/7 and then go for a brutal rampage. THe game would remain the sandbox, it would be the known variable but how your progessed could change, and if the development team thinks of everything it can be far more rewarding then "collectibles" and "difficulty levels"