I'm going to have to bite the bullet and accept that the new AI kicks my butt on Challenging, and drop back to Normal. And that was just the .003 post-release AI. Brad kept tweaking it after that to the point that he lost a game on intelligent, and was getting stomped in another last Friday, though I don't know if all those tweaks are going live (he commented at the time that he wasn't sure if the tweaks would be an overall improvement, or if they just helped the Duel scenario).
So, with that said:
Race: Custom (economy-focused, to fund non-stop colonization)
Galaxy Size: Gigantic (it just doesn't feel epic otherwise)
Opponents: 9, probably all but Terran (While you can select all 10 races, the game acts a little funny, so I'm not sure it's a good idea).
Habitable planets: Abundant
Clusters: Scattered (last I checked, which was after the dev-mentioned tweak, you still got fewer stars if you went with either of the clustering patterns)
Noone should be worried about loosing to the AI that's set to Fool level. The one time I accidentally started a game with one Bright opponent and 8 Fools in a Gigantic galaxy, the Fools weren't even speed bumps. By the time I had half the galaxy and the Terrans had a third, none of the Fools had a third colony. So I started giving them colony ships, and they refused to use them. Basically, as near as I can tell, they're there to practice invasions on.