To 1.: The question is unprecise.
Problematic is fixing the ai, without a big impact on game
performance, at least without the help from Paradox. To not impact game performance, a few calculations, which would have something to do with the actual game strategy (planning), would need to be performed independently from the actual moves (actions) done by the ai, so that ie. these calculations can be done in single player, when the game is paused, or in mp-games on different pcs. Of course in the savegames the progress would need to be stored.
The rest can be done to some degree, but it would involve the use of quiet a few heuristics. And also precomputing the solutions to some mathematical problems depending on the actual game settings and changing some weights according to the solutions. It is more difficult to design the ai, so that it is "good" under all settings, which can be customized in the game settings (galaxy setup), then optimizing the ai for just one of the settings.
To. 2: The question is again unprecise. As the time to fix would of course depend on what the intended goals are.
To 3.: The problem for the ai would be to actually develop a good game strategy, but then the strategy should depend on the goals of the ai, which should in turn
depend on the personality etc. Without a strategy, even with perfect micro and solving quiet a few mathematical problems exactly, the ai would loose in single-player games against really good players most of the time (as it might solve the wrong mathematical problems or optimizes for the wrong goals), but then the goals of some ais might not be winning the game (or denying the player to win). Oh and the ai would need to be able to adept. After knowing how the ai usually behaves - and what is random and what not - it is usually relatively easy to exploit the shortcomings of the ai. Most strategy games would be a lot harder for me, if the others would not make deals with me (or at least not continue to make deals with me, when it is clear that I am the most likely candidate to win and would win, if the rest are not cooperating with each other). - The big problem of most ais in strategy game is, that they are only by name an ai, but otherwise usually a pretty "static" algorithm. And designing a really good ai, well that is complicated, especially if the ai should in the games then compute the results with very limited hardware resources.
To. 4: Again an unprecise question (the term "not-bad" is unprecise). Can you rephrase the question?
ps. After knowing how the ai behaves I am actually really good in coming up with game parameters, with which the ai cannot really cope or where
sadly the ai optimizes for the wrong goals (if it optimizes anything). If you have a mathematical problem which can be optimized concerning different parameters and the used algorithms always use the same priority for optimization, the results can become pretty bad, if because of the settings the priorities are wrong, as ie. in these settings another resource is more scarce then another (or more important). In most 4x-Games raising the research costs/time is such a case (in stellaris also picking enigmatic engineering additionally as an ascension perk might help to not give technologies to the ai cheaply).