I found that the Patronage social policy tree was quite beneficial for keeping my city-states happy. Their relations never drop below 20, I get more bang for my buck with cash donations, and their favor drains less quickly. With all those bonuses, one donation of 500 gold brings them immediately to "allied" status, and keeps them happy for quite a few turns.

If you don't want to invest in Patronage, you're going to have to do their quests or cough up the money. Having good cash flow is critical for expanding your influence on city-states. I find that connecting trade routes to my capital is a great way to boost my income in the early game, before I have a large population and markets/banks/etc. Get those roads out and get your empire connected. As long as you don't spread your cities so far apart that you kill yourself on road maintenance, it's easy money. If you have cities on other continents, remember to build a harbor to connect them to your trade routes.