Slavery is rampant in Volantis and Lys. Pentos isn't much better, with indentured servants who are slaves in all but name--and the only reason they aren't slaves in name is because Braavos forbids it. The cities seem to be largely under the boot of powerful trading lords such as Magister Illyrio. So why are they called the Free Cities?
Valyria needed more and more precious metals, this led to an expansion of their empire. This expansion led them across Essos to the area in which the Nine were founded. However, they were "free" because they were not directly ruled by the controlling power in Valyria.
On the shores of Essos, the Valyrians raised cities, which we know today as the Free cities, Their origins were diverse.
Qohor and Norvos were founded following religious schisms. Others, such as Old Volantis and Lys, were trading colonies first and foremost, founded by wealthy merchants and nobles who purchased the right to rule themselves as clients of the Freehold rather than subjects. These cities chose their own leaders rather than receiving archons dispatched from Valyria (often on dragonback) to oversee them. It is claimed in some histories that Pentos and Lorath were of a third type—cities already extant before the Valyrians came whose rulers paid homage to Valyria and thus retained their right to native rule. In these cities, what influx of Valyrian blood there was came from migrants from the Freehold, or political marriages used to better bind these cities to Valyria. Yet most of the histories that recount this take as their source Gessio Haratis's Before the Dragons. Haratis was himself from Pentos, and at the time, Volantis was threatening to restore the Valyrian empire under its control, so the notion of an independent Pentos with origins distinct from Valyria was a most politic convenience.
However, it is clear that Braavos is unique among all the Free Cities, as it was founded not by the will of the Freehold, nor by its citizens, but instead by its slaves.
The World of Ice & Fire, Valyria's Children
The distinction that sets the Nine apart is not their size but their origins. At their height before the Doom, other cities, such as Mantarys, Volon Therys, Oros, Tyria, Draconys, Elyria, Mhysa Faer, Rhyos, and Aquos Dhaen were grand and glorious and rich, yet for all their pride and power, none ever ruled itself. They were governed by men and women sent out from Valyria to govern in the name of the Freehold.
Such was never true of Volantis and the rest of the Nine. Though born of Valyria, each was independent of its mother from birth. All but Braavos were dutiful daughters, neither making war upon Valyria nor defying the dragon lords in any matter of significance; they remained willing allies and trading partners of their mother and looked to the Lands of the Long Summer for leadership in times of crisis. In lesser matters, however, the Nine Free Cities went their own ways, under the rule of their own priests and princes and archons and triarchs.
The World of Ice and Fire, The Free Cities
Further reading: A Wiki of Ice and Fire: Free Cities
They rule themselves, and aren't ruled by an outside power. The freedom is on the level of the city, not on the level of the individual person within the cities.
The free cities are free of Valyria, from who they broke free when Valyria fell. Braavos which was founded by slaves who fled Valyria rather than breaking free later is a free city in the same sense.
They are self-governed cities owing no allegiance to any empire. Their individual interpretations of civil rights are not the reason for the name; although in Braavos, the title could possibly have dual meaning.
The Free Cities originally were colonies of the Valyrian Freehold - most of them directly, only Braavos was an exception as it was founded by former Valyrian slaves and never directly under Valyrian control, although it still had to fear its former masters. When Valyria was destroyed, they got freedom from their overlords, so they called themselves the "Free Cities".
Compare it to the many similar labels the United States got after their indepence. From the perspective of poor European peasants (slaves but in name too), it was the "Land of the Free" for sure - no aristocrats around anymore. Yet it did have it's very own slaves (from Africa) that only gradually got the same rights as their white neighbours (and one could argue that they are still not entirely equal today).