I've only been considering the problem for about 3 minutes now, and this may be slightly off topic as my post isn't commenting on the quality of CVI's AI, but looking at the question of the feasibility or difficulty of preparing an AI to operate differently at different difficulty levels of the game...
I'm by no means a professional programmer. I've only done scripting for Neverwinter Nights, all self-taught, but I HAVE done AI scripting there. I just never considered working on an AI that changed in difficulty - I always predetermined how challenging I wanted a certain 'encounter' to be, and programmed the AI accordingly. Its not a great walk from NWN AI to Civ AI, I certainly can see how I would script out Civ's AI. What I find attractive about the problem is the AI scaling. How would I go about it? Could it easily be done? Its entirely possible that CVI has already done this, isn't it?
To me, a good AI for Civ would have some way to recognize and respond to human behavior. Obviously it couldn't account for every possible behavior/action (and this, of course, is one reason why a decent player should always win). And, of course, the AI would have pathing for achieving victory. And the two structures would have synergy. GCIII, and other games I imagine, grant AI civs bonus computing power at higher levels of difficulties, but that's not part of this discussion. I'm talking only about the actual coding.
One idea would be to start with a very terrifyingly capable AI script, and at certain points of 'decision' give it a % chance of following through with a decision. The chance would be close to 100% at deity. Then work backwards. A second would be to include in the higher level of difficulties possibilities for actions for the AI to take that it wouldn't at lower levels of difficulty. And yet a third would be to have the AI have preset actions to take at the higher levels of difficulties. Probably a good idea to mesh all of this with the various leader personalities and agendas, but the higher the difficulty, the more commonly seen some of the behaviors would have to be.
So, yes, fairly easy to do I think. Time consuming, but easy. Probably the biggest challenge would be getting AI programmers who are skilled enough at playing the game that they would be able to code an AI capable of dealing with highly skilled players. As we have seen in every version of Civ, one of the biggest advantages the player has is simply efficiency. Never has the Civ AI been capable of matching human efficiency with regards to resource management, be it hammers, commerce, or workers. Why not? The fact that a human can steamroll a deity Civ even with the deity bonuses proves that the imbalance is there, and massive. The AI should be coded in such a way that optimally the major advantage the human player has is that he or she is able to switch strategy and tactics on the fly - the ability to successfully change dynamically in response to situations - more quickly than the AI can. The only reason I can think of for this glaring discrepancy between human efficiency and AI efficiency is that the programmers are coding AI without knowing enough about how resources should be managed. Possibly not a comment on their playing abilities, as, after all, they most likely are far into the programming while much of the 'concrete' game is still being made.
I'm not too worried about the AI in CVI though. From the viewpoint of someone who has tinkered with AI, it appears that a number of the agendas and abilities were created with AI in mind. I expect we will see some major AI updates in the first few patches because the dev team WANTS to have a good AI, and have been paying attention to that throughout the design process. But you aren't going to have a challenging AI at deity right off the bat, not with such a limited amount of testing at that level at a point where the rest of the game was fairly polished. AI tweaking while the rest of the game is being worked on gets to be a real black hole... a push here becomes a pull there sort of thing.
As for some these AI decisions we are seeing in the videos, well, its Prince. PRINCE. Maybe something to worry about, maybe its not. Because there is the possibility that there is nothing to worry about, and the ramifications if there IS something to worry about I don't really see as WORTH worrying about, I'm not going to worry about it.