Mercenaries of Toutus

This is not a complete list, but just the most notable and famous of the mercenary bands around the west coast of Toutus. You may notice that Teiglin does not feature much - as a large kingdom with its own army, it does not need mercenaries, though they may be found around the borderlands along side adventurers. 

Tancrad's Motley Mariners - Tancrad Anchorhead (12th level fighter, unaligned) is a mercenary fleet commander with 5 ships at his disposal. He is based in Trislem in the Walrus Freehold, and usually has one or two of his ships there. He also does business in and around the Varreshiss Islands, and there is often one of his ships in that area.
Each ship is a caravel with a crew of 50, made up of many different nationalities, appearances and a few different races (a number of dwarves and halflings are among the ratings). They are all combat trained (1st level fighters minimum) and none are obviously chaotic - some discipline and standards of behaviour are required. Many are legitimate sailors, but some are reformed or refugee pirates and buccaneers either turned honest or just lying low.
Tancrad usually hires his ships out for exploration, trading in dangerous waters or amphibious raids. Anti-piracy patrols and other dangerous tasks will require extra hazard pay.

Sterin Clerical Services - 20 clerics of Partheusa are based in Sterinport and on hire on a daily basis, either the whole company or a contingent of 3-5 (never fewer - they like to watch each others' backs). They usually dress in chain mail, with surcoats and shields bearing Partheusa's emblem (a blacksmith's hammer on an orange background).
As befits followers of a goddess of trade and craftsmanship they are professional and detached about their work and generally offer the range of clerical spells up to 4th level, including healing, divination and protection. They often work along side more combat-oriented mercenaries as combat medics, or dealing with limited outbreaks of disease or undead.

Svarrien's Company - These are a relatively conventional mercenary company of 200 men split into 4 platoons of 50 men each. They are all human fighters of at least 2nd level and are equipped with plate mail and either wield spears, shields and swords, or swords and light crossbows. They fight in formation, with the crossbowers firing over the heads of the spear and shield men who are braced to fend off cavalry charges.
Svarrien's Company are based in Sturnornel Fort, and are based around a core of survivors from the Urdus Ducal army who fled eastwards during the Summoning. There is still some sort of loyalty towards the humans in the area, though since the duchy has collapsed they are now interested in money rather than feudal obligations.

Uldur’s Scouts - a company of human light cavalry with studded leather and fur armour, lances and maces who are based in Walrus City and go out on patrols on the Icemud Tundra, visiting trading posts and trappers. Like Svarrien's Company, they have some loyalty to the city, and are unlikely to betray Walrus City or attack its citizens and traders, but they do expect to get paid, and will often moonlight  in side jobs when things are quiet around Walrus City itself. Uldur himself was killed during a battle in the Wars between the Empires when Bursian forces attacked Walrus City, but the company still carries his name. There are believed to be 75 in the company, which is often split into patrols of 12 each. 

Grundil's Quarrellers - In Stalim in the Walrus freehold among the 550-strong militia are Grundil’s Quarrellers, 150 dwarf crossbowmen originally from the Grulven Mountains who now act as mercenary guards. They are paid by the city council and as such are relatively loyal to the city as a whole. The dwarves are used in defensive duties, including manning the city walls and assisting the other militia and city officials at the city gates checking visitors and traders going in and out. There is the unofficial role that it keeps the dwarves of the Grulven Mountains on good terms with Stalim and there is a turnover of dwarves coming to join the company for a 3 or 4 year "tour of duty" and going back to the mountains to tell the other dwarves what their human neighbours are like ("Alright I suppose, and their ladies are leggy, but they don't have proper skill with metal and their beer is like watery yak pee")