I strongly suggest checking out the original "Sword of The Stars".. if you want fair non-cheating AI, challenging both in diplomacy, battle, strategy, where each AI wants to win just like HUMAN. Random tech trees are amazing, making each game different. The essence and philosophy of the game is it's simple and easy to play, and hard to master. It takes away all the useless micromanagement and annoying tinkering with sliders and numbers and allows you to focus on grand stategy (fast turns etc)
I'd start with vanilla game, latest patch, and once you have the grip.. add expansions 1 by 1 and play the new races and newly introduced mechanics. Each expansion also advances the story line and evolves the game and its mechanics.. adding trade.. etc.
it is closest thing to Master of Orion 2 ever made, if not even better.
It is sad to note that Sword of the Stars II has followed up the failure of Master Orion 3... simply doing complete opposite of what the SOTS1 was all about... too many sliders, overcomplicated tinkering from turn to turn, too many things happening but giving user very poor feedback, ships move like RTS, and... most of all.. its so overcomplicated that AI is totaly dead with diplomacy, designing ships, tactics, and most of all... managing its ecconomy (collapsing on itself).
I wish they kept the simplicity and speed of SOTS1, and simply added modern grapics, more modular ships, kept one planet systems (battles near planets only)