Here's some more insight on the performance issue I had: it was not related to an uneffective algorithm (I am using a decent pathfinding and FOV calculations) - it was related to the way I was calculating the ranged attack possibilities.
See, the issue with calculating whether a character can/cannot attack someone does not include regular raycasting from character's position to its target. See this targeting/flanking schema describing how this works in xcom:
The thing is that I need to perform calculations for the potential positions that a character could be at. For attacker, these are the positions on the sides of a high cover - which simulates the character leaning from the cover and making the shot.
Additionally, same works when trying to shoot a character who is hidden behind a high cover - I needed to check whether a hit has been made with any of potential "leaning" positions, and this counts as a hit.
Now, when the AI is determining its next move, it needs to gather information about all the potential threats and opportunities - this includes calculating ranged attack chances.
So basically a character needed an extra instance of a sub-object with collision information - to be able to work with the "leaning" mechanism. And my problem was that during every such check I was creating a new instance of sub-object. With collision information and stuff. And then it was destroyed immediately.
And then this creation/deletion repeated itself.
For. Every. Goddamn. Possible. Location.
So this quickly got out of hand. These short-lived objects were forcing the Garbage Collector to perform a lot of cleaning (note: I am writing this stuff in C#). Profiler in Unity did point me in the correct direction with this, so I was able to fix the issue with reusing the same instance of an object with a collider in every case.
So that's the long story behind performance issue.
Now, what's the progress of the game itself?
First of all, I did some more bughunting and managed to fix issues with calculating hit chances. Again, it was related to the fact that sometimes the attack does not occur from the original position of the attacker, but is about them leaning out of the cover.
See this screen:
Rat is clearly flanked here, however it does not have its cover displayed in yellow (which is used to indicate it being flanked). On the other hand, the player character (wielding this badass shotgun) is flanked. So clearly the calculations were done wrong; anyways, that's fixed now.
The second big thing was allowing some of the movement to be displayed in parallel. So now every time an enemy pod gets revealed, its members are performing their activation move altogether:
Note that this only occurs for the pod activation phase. During normal enemy turns, only a single enemy moves at a time - this is to make sure that the player knows exactly what is going on.
That's it for now. Grab some more screenshots/gameplay gifs: