Actually, I usually don't have "enemies", just friends and neutrals that I want to see things my way.

As you might guess, I tend to play Universalists.
I often put cultural palaces in both my sectors and their sectors. I have yet to receive a demand for turnover. It may be that I do not build starbases in sectors where I am not at least competitive in influence already. I am just not sure which is more effective.
(The following from the Encyclopedia)
Here is how sector influence is calculated:
1st: Your civilization's total monthly influence (i.e. all your star systems added up) / (Number of sectors in the galaxy).
2nd: Then it looks at how far away from a starbase or star system that sector is and the further away, the weaker your influence is.
3rd: It looks at what starbases are doing in a given sector. I.e. are they magnifying influence there.
4th:: Then it multiplies that amount by 5 (you'll see why in a second).
5th: Then it does adds the influence from the adjacent sectors to the total without mutiplying them by 5 (this way, local influences weigh much more strongly but what's happening in other sectors matters some too).
(End Encyclopedia entry)
Alas, the 5 steps are not very specific. Is a starbase the same as a planet? Or not? If a starbase is the same as a planet, then creating the cultural palace in their sector is going to be 5 times more effective than doing it in my sector. On the other hand, if a starbase is 1/10 of a planet, then I am better off doing it in my sector with a planet, even though I give up a factor of 5 for not being in the same sector as the target planet.
Alas, I am still getting my feet wet with this game. Right now I have one underway where I have two allies, and am picking up the planets of minors by military might because I cannot get them by influence. Maybe I will get to being a military genius, but am not there yet.