New City States: Which Ones Should be Added?

[Zaarin]

But those mercenary CS are only useful for a very limited time frame and I think envoys spent in a bad way. Interesting idea though.
I'd like to have maritime CS back

A good point. Perhaps they could find a workaround. Perhaps mercenary city-states could have some other (somewhat smaller) bonus as well.