I mean the important thing about implementing a decent espionage system (including counter intelligence) is making it an active system that people engage with.
I always find it annoying when people use the "it's not fun to be on the receiving end of" argument for keeping espionage weak, for the same reason it would be dumb to apply it to warfare - if being on the receiving end is annoying because it's essentially just penalties you can't control, then you need to let people have more control to make it more fun.
For example:
Increase the number of agents available, rather than having them be 1:1 with envoys. Envoys can be assigned to spy networks, where they can, among other things, recruit agents who act similar to HOI4 spies in that you put them in a system with a planet and they start to build local spy networks on the planet as well as relevant connected systems (e.g. within the same system, within the same trade hub, within the same sector etc.). Most espionage actions are then done in a local way and often have a side-product of creating crime for example: Academic Espionage targets an empire's research worlds in the network, giving you boosts based on the outputs of those worlds, but slightly increasing crime. With more powerful network, you get a greater effect, but the crime effect is larger too - this has the side effect of tipping off that something is happening in the system (though all espionage related crime, as well as a randomly fluctuating base amount would be lumped together to obfuscate it somewhat).
With more localized networks, it also becomes easier to build network in nearby parts of enemy empires - it is easier to run espionage on the near side of a neighboring empire than the far side, and it's easier to do it on close empires than far away ones. Megacorps would get a bit of a buff in that it would be easier where they have branch offices, with a very large local bonus for Criminal Megacorps.
Counter-espionage is done in two mechanisms - firstly at the empire level by assigning envoys to build up counter-spy networks within your own empire: this general method has some effectiveness in mitigating enemy activity but is not very effective at it and mainly serves to help you identify who is doing espionage against you - you then assign empire-specific counter-efforts which are more effective in stopping that particular enemy.
By turning the whole system into something more active, dynamic and space-localized (rather than a single screen at the empire level), it becomes more of an alternative to war in terms of both the level of counterplay and hence the amount of teeth you can give it.