Some brief ideas for making the AI tougher, without 'cheating':-

1) Concentrate more on 'yellow' techs - the power of diplomacy and influence seems under-rated.
2) Build influence Starbases to expand their empire and place these near opponents planets on the edge of your influence range.
3) Declare war and then attack - don't declare war and then give the player x amount of turns to prepare for war.
4) Try not to declare a war on 'two fronts' as this can be disastrous - part. evil AI's.
5) Be prepared for a war of attrition. E.g. targetting an oppenets largest planet etc, will deplete their their military machine. Likewise guard your key planets well.
6) Assess losses of ships and planets Vs your opponent to establish that things are going 'badly'.

Any other ideas?