One problem here is the conflict between player agency and challenge. If you set the AI to a higher level, the game will be more challenging. Mostly because the AI just cheats more, not that it plays much better, but still, more challenging can be good. However, if you set the AI to something that is challenging to you, chances are that it will be one of the AI nations that reaches the next age first. Which means you are losing player agency, because it isn't you who is selecting whether you'll play a normal age, a crisis age, an alternative history age, or a victory age. In my current run, AI Russia caused an age of plague to appear. That was interesting, because I hadn't played it yet, but definitely messed up my plans for the game.

The same problem appears on the rather basic decision of whether you would like to play a game of peaceful expansion, or a game of military conquest. The diplomatic system of Millennia is rather primitive, and the AI decides whether it wants peace with you based on whether they feel stronger or weaker than you. Thus if you set the AI to strong, they'll constantly decide to declare war on you, and none of the options in the diplomatic system seem to be able to change much about it.

Much of my restarting was done to modify my distance to the enemies. A typical mistake is to start a game with the default settings of continents, medium, 8 players. The continents map always has 2 continents, and about 40% of the map is water between those continents. On a medium map, this much water leaves relatively little dry land if you divide it by 8. So the AI, which is good at aggressive land grabs, will seriously hem you in. Even if you go warfare, and take more territory, you can't currently raze regions conquered from the AI, which means that you are stuck with a network of regions far too close to each other. The medium pangea map would already leave more space for 8 players, due to fewer water tiles. But you could also modify the map size to large, or reduce the player number to 6. In extremis you could do a medium continents map with just 2 players, which would give one continent to each of them, and no interaction until deep water travel is researched mid-game. Of course giving yourself too much space, on a larger map with fewer players, also takes away a lot of interaction with the AI. Thus one needs to experiment a bit which is the best compromise between space and interaction.

To make matters even more complicated, the devs released a "patch zero" yesterday, but the balance changes in that patch only apply to new games. So again I am not certain whether I will finish my current game or start over once again.