First off, the only 4X game I've had a chance to play is GalCiv, and I haven't been keeping up with these forums too much. I apologize if this has been discussed before. Anyways:
What if anything more than basic communication wasn't instant? Instead of sending research across the map instantly you have to dispatch a runner. If you send an ally some swords, a new caravan is created just for that. Upgradable, of course. From, say, runner to horseback, horseback to horseback chain (Pony Express-ish), from horseback chain to semaphore chain (Discworld FTW). Spells could be learned as well to circumvent this.
Basic communications (Just talking to another player) would of course have to remain instant, as people would just get on Vent or IM otherwise, or would just get frustrated.
Couple of reasons:
This adds a bit more to making alliances. A highly war-like society isn't likely to upgrade this, and so will have a harder time negotiating anything, while more diplomacy oriented cultures could enlist the aid of their allies that much faster.
It also adds the concept of intercepting such messages and cutting off empires from outside communication. If they don't guard that caravan properly, perhaps you could beat their faces in with their own swords? Perhaps you could capture the rider to steal the latest tech/spell, or maybe even bribe them so that the opponent may not even know you just stole their secrets. Semaphore could be harder to break due to being a line of sustained towers, and maybe have encryption and decryption to intercept and prevent intercept of messages.
