Part of this is historical cribbing. GRRM is borrowing from the military tradition of Carthage, who relied extensively on mercenary armies. Carthage was an oligarchic plutocracy, with wealth being the prime dictator of who had power in that ancient city. A lot of wealth could translate into a lot of mercenaries for the family. The Free Cities don’t put especial importance on martial prowess the way Westeros does. While it might be remarked on that a particular noble son is a skilled warrior, city-fathers of the Free Cities are typically wealthy aristocrats relying on slave soldiers and mercenaries to advance their agenda. Even the tigers of Volantis aren’t the ‘lead-from-the-front’ nobles the way many Westerosi young men are. These wealthy aristocrats use their wealth to prosecute their wars, so mercenaries would be in high demand over in Essos.
Second, magic on the whole isn’t very prevalent or reliable in the time periods before the modern one, and there’s arguments to be made that it still isn’t the most reliable thing now, even after magic returns to the world in a big way. Melisandre’s visions are home to misinterpretations, and she even admits that she makes herself look more powerful than it actually is. Relying on magic when it could fail you when you need it most is dangerous. Prophets seem to think that the future is unavoidable. Renly is destined to die, but the vision of him leading an army against Stannis comes true even post-mortem, so it’s not something that I, as a general, would bank on.
Magic is too dangerous and unreliable to base a military doctrine around it in the Planetosi world. The Free Cities are fantastically wealthy, and so they pursue a military doctrine that makes use of their advantages. Coupled with an active slave trade through most of Essos, and there’s no surprise that the mercenary tradition would flourish on the eastern continent.
Thanks for the question, Anon.
SomethingLikeALawyer, Hand of the King
In addition to Carthage, the hiring of mercenary companies was endemic to the city-states of the Italian Renaissance. The condottieri of Italy were known for changing sides at a moment’s notice and for a price, running away rather than engaging in a fight where they’d take heavy casualties, and being keen to take over cities where they could – hence Machiavelli’s famous denunciations of hiring mercenaries in The Prince.