I would really like to see the way City State quests work changed in a major way.
1) Quests like "who can gather the most culture/faith/science" should be changed so that instead of counting the culture you collect for your own empire, this should be a competition between the players of donating the resource to the city state, with the winner being the player who donates more, or rewards given based on donated amount. The current system tends to favor snowballing, because the leading civ generally gets a lot of free influence this way.
2) In general, donation of gold should be toned down. In Civ5, winning diplomatic victory is basically an economic victory: Who can earn more gold to bribe all city states. Gold quests are fine, but the city state should only accept gold when this quest is active. Also, rather than being an indefinite amount, it would be better if it was a certain amount - for instance, city state X need 1500 gold for XX project, and then you could choose to donate (250/500/1000), but once the quota is met, the quests goes away. This should be global for all players, so that if you choose to donate a lot of money, you take the opportunity away from other players. This makes it more competitive.
3) Quests in general should be global, i.e. for all players. Free-bee quests (like "they want you to discover a new natural wonder" or "find the location of player X") should generally be toned down - while mana from heaven is nice, the occurrence of these quests can skew game in a rather unhealthy way as it is now imo.
4) "Pledge to protect" should only have effect if you actually keep a number of units close to the city-state - similar to how the Autocracy perk (Gunboat Diplomacy) works.
5) A minor thing, but something that really annoys me in Civ5: When you and a city-state is at war with a common enemy, you should get influence from killing enemy troops threatening the city-state, similar to how you get influence from killing barbs in their territory.