Hmm. On fool, beginner and sub-normal I found it not really a problem to dominate -- at least on large maps, which probably give human players a bit of an edge due to better strategic grasp. On normal, I need to try if, say, I want to combine a massive military force with always having on-par tech and getting every trade good and galactic wonder before AIs do, even with a decent start.
It's far less brutal than King of Dragon Pass, though, where you're struggling for survival -- not dominance, merely survival -- for much of the early game, between famines, feuds, Chaos outbreaks, diseases...
Psychocircus -- Five days, and genius level already? That seems a bit extreme... bear in mind that at genius and incredible, the AI gets bonuses (e.g. extra points to spend while setting up its racial traits). At Intelligent, it's even; at anything below, both racial traits and behavior (ability to notice things, for instance) get penalized.