Actually, just guarantueing their independence works fine, if you have influence to spare.When in doubt, bribe them.
More importantly then increasing relations, it as well increases trust, making it more likely for the AI to accept diplomatic actions.