I've played a few games against "Genius" level AI opponents (one step below the max) and have noticed a few things the AI consistently does poorly, apart from the obvious planet specialization problems.
1) Small Fleets: the AI seems to either be unable to group its ships or to severely undervalue doing so. I often see 8 or 9 fleets of 2-3 ships each, which are all mowed down without losses by my own fleet of 6 ships. Even thoughtlessly-composed fleets with essentially random contents would be a huge step up from individual ships. Having the AI rally ships to some location under its control, and then waiting for a certain fleet size (even a semi-random size based on current logistics ability, so that there will be *some* large fleets) before deploying to the warzone would improve things enormously. I have even seen the AI split large fleets (usually in orbit of a planet) into smaller fleets, or come across stacks of individual ships in the same tile that are nonetheless not in any fleet. In addition to being ineffective, this is not very fun to fight against--I want to see my best fleets square off against my opponent's best fleets, not click a hex repeatedly after waiting for each fast combat to finish.
2) FOW problems: There are a number of ways to exploit the AI's ability to see the entire map. For example, I can tell which systems contain habitable planets by watching the direction AI colony ships try to move. I can also manipulate the movement of enemy fleets by allowing an unarmed ship to float nearby out of movement range. A lot of this would be fixed by making the AI aware of only what it can actually see, which is something I know the devs are working on.
And, some things that are probably not "low-hanging" fruit:
3) The AI seems to weigh in-game calculations of civilization power (esp. military power) too highly, and these metrics are calculated in ways that are not useful. In a recent game I stopped military production to watch an AI Krynn player's reaction--once they had achieved slightly more than twice my own military power, they declared war. That "military power" seems to result from a count of ship hulls by size or maybe a count of raw firepower/defense points; either way it does not seem to take into account other technologies. In my game, despite being so far behind in "military power", my ships were able to trivially defeat all the Krynn fleets. It's hard to guess at the underlying mechanics here, but it seems that the contribution of short-range, high firepower kinetic ships is overvalued when calculating military power, and that other supporting technologies (move speed, tactical move/evasion, accuracy boosters, logistics, etc.) are not considered.
4) Declaring war, then doing nothing: the AI seems to often declare war when it is unable to actually prosecute a war. This seems especially common against aggressive AIs that are currently engaged with other opponents--they declare on me (usually due to excessive military weakness), and then nothing happens because their ships are all elsewhere. This seems to happen too often for it to be the result of some simulated diplomacy between AIs. This might be difficult to implement, but I think it would help to have the AI behave as though it were at war for several turns before actually declaring war; this is essentially how I operate as a human player.
The biggest single issue by far, though, is the small fleets allowing the AI to be defeated piecemeal by an inferior force. Changing this would make a big difference in the "feel" of the game