I've given a lot of thought to the differences between Total War games and Paradox games.
I think that the fundamental difference in AI is because of the underlying game. CA has in my experience bitten off far more than they can chew with the last three games. Their design focused on the idea of adding new features each time. There is a big problem with this. If your computer game is going to primarily focus on player vs AI gameplay, ever bit of complexity you add, every choice that the player is enabled to make, must be compensated by additional work on the AI. If the player is allowed to make X decision, for the AI to compete, it also needs an effective algorithm to make X decision in the best way. With the advent of Rome Total War, the decisions that can me made grew exponentially. The map became an enormous grid of an insanely large number of possible battlefield combinations, and an insanely large number of possible paths. This was put forward as a new and exciting feature, and brought in a lot of sales for CA. However, CA could not exponentially increase their investment in AI to compensate.
In Medieval Total War (the first one) the map is a risk-style board of regions that connect together. Each of these connections in each direction has a terrain setup. It was much, much easier to create an AI that was effective in its decision-making in such a scenario. Thus, the AI in MTW can be made to be much more challenging and seem much more intelligent than that of RTW, even if RTW had 10 times as much effort put into the AI.
This is in my opinion a big part of the reason that Paradox Games have better AI -- the fundamentals of the game design are well thought out with the AI in mind. Instead of creating new features to advertise to people who have not yet played the game, Paradox has wisely expanded their complexity in ways that the AI can still be effective. Without access to the source code, I naturally can't know how their actual AI coding compares, though I have a strong hunch (influenced by knowledge of C++ and use of data files, and extensive examination of the data files for both TW and Pdox games) that the Paradox programmers are much more efficient at programming their AI and making maintain-able code.
So, the argument is often made that CA didn't do a worse job, their game was so much harder to make, &c &c. The fact is, CA did not plan their games well with this in mind, either knowingly, considering the money they make off of new features, or unknowingly. Either way, I conclude that they did a worse job at planning their game from a gamer's perspective (again, from a business perspective, they make a lot more money, and this is very much because of their constant expansion of the features, since the players don't know how the AI will handle them until they have actually bought the game). Paradox on the other hand from my observation gives a lot of intelligent thought to the fundamental design from a gamer's perspective. Which is why we don't have a lot of ambitious cash-cow products from Paradox that disappoint everyone.
And it shows, consider the vast difference between the spirit of the Total War forums, totalwar.com for instance where criticism is rampant but censored, and twcenter.net where the criticism is also rampant but there is much more freedom to discuss it. It is clear that a large percentage of forum-goers who purchased ETW were very disappointed. Look at the Paradox forum, and unless 90% of rants are instantly deleted without anyone knowing, it is clear that the forum fanbase is very pleased with the job the developers have done, and are not disappointed -- with the exception of EU:Rome which I think most of us agree was not representative of Paradox typical work. Rome is a negative for PI, no way around it.