How feasible would it be, for the civic 'City-States' to give a production bonus (50% or 100%) for building a 'Palace' to move a nation's capital? It strikes me that most nations that fit the 'city states' model (ancient Greece, classic Maya, Renaissance Italy) didn't have a single long-term capital so much as a series of local hegemonic cities, and making it easier for such civs to actually move their capital would make it a bit more likely for that to resemble real history.
Another possibility would be for the 'City States' civic to give a temporary bonus, something like "+100% culture in your capital for the first 20 turns after building a Palace" or something (+50% culture, +25% production in the capital?). That'd give such civs a reason to invest the time and effort in moving their capital.