One more thing I saw was that the AI's attempt to use Brownian motion
for colonization was almost completely ineffective. This may have just
been because the engineers couldn't use transports, but it also seems
that the engineers should be able to more carefully pick a spot to build
a civilization. Perhaps Brownian motion is what you want when you don't
have any effective explorers, but when it comes to colonizing planets,
it is essential to know where you want to colonize and go to precisely
that place.
I've been thinking about early game strategies for the last few days as
a result of the discussions here, and while I'm not much of a C programmer,
I though I could present some sort of plan for discussion. The following
is based on my experience with "terrestrial" Civ-style games (Civ I, II,
III; SMAC/X; Colonization; MOM; and others); IMO space-based games (MOO I,
II; SE III, IV, IV Gold; etc.) require a slightly different approach. In
more general terms, I think the difference is whether terrain is fairly
continuous (Civ), or more discrete (MOO). I also assume that there is some
sort of fog of war / unexplored map setup, although it should be
generalizable to situations where the whole map can be seen (mostly by
truncating the initial "view" distance to some reasonable limit for
purposes of settling).