I have always found conquering everything that moves solves my influence problems, but as you want to turtle, building things helps, especially happy buildings. Also, I would think that spies and diplomacy would help - marry off a few princesses, make some alliances.
However, in the end, you can't beat a bit of conquering - maybe you could engineer a small revolt, which could be crushed.