We don't need to worry about completely unintelligible (to us) Lovecraftian aliens. If they exist and are even
interested in looking for alien life themselves they'll have equally unintelligible (to us) methods and motives.
Life on Earth is varied but has a couple common characteristics. It's not coincidence Earth life is carbon based. Carbon is pretty common, a lot of organic chemistry involves similarly common elements but also offers the complexity to build some really specialized molecules. It's more probable than not that carbon based life is one of if not the most common chemistries.
Water is also pretty important for life on Earth. This is also not a coincidence as water is a very interesting molecule. It's a mild solvent so it enables a lot of chemistry to occur. It's composed of plentiful elements and is found throughout the universe. Other molecules have similar properties but most are more complex and aren't quite as versatile as water.
We are concerned with alien life that is at least somewhat like our own. We're interested in species (should they exist) that recognize the utility of radio any optical astronomy. Cthulhu may not give a shit about radio astronomy but that doesn't matter.
The universe is filled with radio emissions, any intelligent species that discovers electrical theory will end up being able to detect it. Natural radio emitting phenomena tend to be temporally cyclic. So even if a particular species doesn't think "linearly", lots of phenomena are linear in the time domain. Their radio astronomers might find it weird but they'll know linear events exist and have a way to express them.
So radio is a pretty good medium to send messages. Messages encoded in the level of math needed to understand electrical theory well enough to build radio telescopes will likely be intelligible by those telescope builders. The same "linear" understanding species would need to understand pulsars or radioactive decay will let them understand linear intelligent signals.
Interstellar communication is likely to only be one-way but there's some common denominators that logically fall out of the effort. They won't work for every kind of species that could exist but you don't need to target every possibility, just a reasonable subset.