Well, my first thought is that in order to hide/sneak, we can't have the AI be everywhere the way it is in AIW1. Space is big. We need there to be parts of space that the AI can't keep a watch on 24/7.
Some thoughts:
* We'd probably need more neutral systems to start the game. Maybe the AI only has periodic patrols in some areas, instead of a garrison in every system.
* Implement limited sensor ranges for most units.
* Maybe the AI relies on a network of sensors (which could be hacked) and automated "turrets" (Guard Posts).
* Maybe ships could hide (from long-range sensors) near asteroids.
* If you really want it to feel like a covert op, the brute force technique should incur increasingly vigorous responses. One sensor blowing up might be random pirates, but if several sensors in the same area go offline, the AI should send in a significant force.
* I think a key question here is whether/how much micromanagement is acceptable for the human player to "sneak". If ships need to follow a particular path to avoid enemy sensors, does the human have to manage it, or will the game try to have the ships actively avoid sensors? I personally find it fun to micromanage important missions, but others might feel that that's too low-level.
* Another big question is "How much should the AI know about the humans at the start of the game?" Does the AI know where the human home base is? Should part of the challenge for the player be keeping the AI from finding their base? In this scenario, perhaps the base has a cloaking field that can withstand a casual patrol, but a serious search will have a ship with tachyon sensors.
In any case, to make any kind of covert activity possible, it becomes very important that the AI's sensor capabilities, whatever they are, be well-defined, limited, and understood by the player.