There is another option here and that is to introduce a player v player mode. This game can be a lot like chess. The first time you beat the AI you feel pretty good but then you learn how the AI behaves and you start to beat it easily. It's extremely hard to make the AI adaptive.
So changing the game to multiplayer would be a more positive move than making the AI more difficult. I can think of at least 3 game modes that would be entertaining. One v one, or even a team based strategy. Then there could be a war zone style island defence game, many carriers each defending it's own Island.
You could even try a - one carrier, many players - approach where up to 9 players control a single unit in the game.
By the way if you made this an expansion pack I would buy it.