I don't think it is an issue of size, so much as it is an issue of planet #, and star density.
It seems tome that if the AI has only a few planets, or if there is a great distance betweeen empires of empty space, then it has trouble really getting going, or conducting expansion/war.
i agree. 1 player on a tiny map with abundant stars/planets/habitables will do okay. 2 might work, and 3 would easily push it to that breaking point. AI players have difficulty when they're crammed together without enough basic resources. of course, so do i.
star density seems to affect the colony rush more than the number of stars. when stars are crammed together, players in a good position to expand will of course do better. when they're evenly dispersed, AI that handles the rush does better. i prefer loose clusters to give the most play between the two. of course, i find that on sizes below large, the star density algorithms don't do nearly as much as they do on larger maps, which is only common sense.
the following is based on no systematic play testing, it's just my off-the-cuff sense of things; setting planet factors to max, the following map sizes could handle up to the following number of AI players:
tiny maps: 1-2 AI players
small maps: 3-4 AIs
medium maps: 4-7 AIs
not sure what you're looking for, myself. i personally love larger maps, just with fewer planets.