At challenging, the AI does not cheat.
This topic has been discussed unto death, but here goes.
AI on gigantic maps can be easily beaten in the colony rush phase.
From Tough to Painful (forgot that one Norad), I can beat the AI in colony rush and beat them in research even though they get a bonus in Painful - yes I know a small bonus.. working my way up slowly, no time to play
From your comments, you want to play this game on Tough.
Suggestions, practice...practice...practice.
Learn to control the tax slider, spending slider, specialization of planets, Social:Military:Research sliders, morale, diplomacy, which research to go to in what order, ship design....etc.
You can not expect to keep the sliders in its default settings and expect to beat the game.
That will work in normal and even challenging but not in tough or higher.
Start of game, build a colony ship with 2 engines and colony pod.
This gives you an unfair advantage to the AI since they design new ships once a game year.
Using the tax slider and the spending slider, you can build the colony ships fast enough using direct purchase at key times controlling the amount of gc in bank and if lucky enough to get more gc via anomalies.
Expand, expand, expand....you should easily beat out the AI in expanding unless random chance reduces star options in your immediate area.
Go for anomalies...get the bonuses from them.
Research the proper techs in order - depends on the game - get the higher engines if you need more speed, at a certain point it adds +1 speed to all ships that you have...look at the research chart to find out which ones do.
Please dont make the assumption that the AI cheats without at least some basis of understanding the game mechanics.
It seems simple and to a degree it is, but the interactions of all the simple mechanics make it complex.
This is soo true with economy.
I dont think anyone really understands how it works except to say - population!
Hope this helps