Master of Orion II multiplayer is typically the place to find challenging games. What about times when you just can't find an opponent or don't have that much time? The single player AI just doesn't work for practice games in single-player mode. Here's what I did to help make the AI a bit more challenging.
After starting MOO2:
1) Click Multiplayer->Hotseat->New Game
2) Do the game setup as if you where playing multiplayer
3) Keep adding custom human opponents with good race picks.
4) Start the game and play the first turn for the AI then save it.
5) Click Multiplayer->Network->Load Game then load the AI saved game.
6) Click start game after 1 person as joined.
7) Click yes to confirm start with AI opponents.
Another way to do this would be to save your first turn from a multiplayer game then load that with AI opponents. The idea is that with stronger race picks the AI will have less of a disadvantage. On Impossible, with good race picks, the AI plays about as good as the average new player. They still make lots of mistakes but it's better than just using their default race picks.
The main flaw with the MOO2 AI is that it has MOO1 mentality associated with one habitable planet per system. Instead of building colony bases it tries to expand to get the most systems possible. Since colony bases are cheaper than colony ships, this is inefficient. It also errors when building ships; tending to use lots of bombs and few weapon mods. That doesn't work for well ship-to-ship combat. Another problem is that it values a systems position over it's actual worth. It'll populate and defend a poor planet that is near a rival rather than colonize a back-water rich planet.