I tried my first game on Tough, and decided to use the medium map to apparently make it more challenging.  5 other races.  I played stock Terran.

  I didn't speed build shipyard anywhere, and had a decent colony rush, netting me about the same number of planets as everyone else.  Nice thing about the smaller maps of course is that you meet everyone fairly quick, and have plenty of trade opportunities.

  The AI did a good job of cranking its pop and building its empire.  I seemed to be in last place for everything.  But, I continued my pragmatic approach, being ready to defend any invasions.  I saw the Drengin were sending troop ships, so I popped my prag points, and declared neutrality for 50 turns, although I was well aware of their intentions, as we shared 2 star systems.  No crazy sneak attacks, I just needed about 15 more turns to get my fleet finished up.

  It was a cakewalk...I would say the main problem with the AI (and I'll try suicidal next game) is that they simply DON'T focus on logistics and keep their numbers together.  Too many ships by themselves, or not even half full on their logistics.  No, I wasn't raiding behind enemy lines either, or stalking rally points.   I killed 205 ships, I lost 1 (lol, I think that was a scout).  As well, not being the first time I saw this, there were some occasions where there were multiple single ships sitting on a stack, just waiting to get slaughtered. 

  My fleets simply demolished every ship and shipyard within my range.  I had to wait a while to get my money planet in full gear, and get my 3 production/troop planets cranking at full steam, before I went on full invasion mode.  But looking back, it wasn't more difficult on the smaller map, simply because Human fleets can lay waste to the AI.  Its just not fair.

  They can give the AI as many bonuses as they want, but the best improvement to the AI to give a challenge, would be for the AI to consolidate its fleet power, with high logistics.