-In general people tend to get upset when the AI stealths up on a player, they feel cheated and angry.
I don't really see the problem here.
-The AI either wouldn't be able to easily defend against Stealth, as even a normal player couldn't, especially on larger maps. And when the AI didnt see you people would complain about the AI being "stupid" even know its not its fault as it couldn't see the ship. Or if the AI could see the ships, people then complain about the Ai "cheating" even if it had the techs.
Regarding the fact that most of your attacks focus on operations deep inside enemy territory, the ai could deploy detection ships (with about 4-5tile detection range) in areas it classifies as "important". Possesing stealth tech should trigger counter research in this area, since you can actually see the techs of the enemy in the diplomacy screen.
-Then you have the problem of "well we have to add techs and things to counteract the stealth.. But then if you start adding counters to it then what's the point of having it if everyone can just see the ships anyway. Stealth would be so powerful everyone would use it and also get all the techs to counter it, so it starts to loss its usefulness.
I suggest adding stealth detectors with about 4-5 tiles range, limited to one per ship. In contary stealth ships (when cloaked) would need to have 75% of their movement points to attack, so they need to close the distance before attacking, while still retaining their usefulness when used right. To prevent stealth spam, i would suggest that stealth devices cost
strategic ressources like 3 thulium per device, so stealth ships are extremly expensive but have the ability to change the course of an entire war, if used correctly.
-What happens when you try and move a non Stealth ship onto the tile of an opponents Stealth ship, does it just attack them, do they unstealth.
This should trigger a battle with an combat advantage for the stealth ship, since the enemy is "suprised" spotting you.
This way, one could implement balanced stealth with only adding 2 new modules and without making huge changes to the game.