Gale is a kind of complicated city, so my best advice is to wander around and make sure you've covered the entire map.
When you first enter Gale you'll find that you can't get in through any of the gates. Make your way to the northeast corner of town and you'll find a man standing near a trap door. This is Pasi and he'll give you permission to use the secret passage into Gale.
The secret passage leads up into a storeroom in one of the inns in Gale. Make your way into the common room and talk to Langley, the innkeeper, if you want. Sitting at one of the tables is Alba, who sells Skribbane.
Just to the south of the storeroom you enterted through is the inn's kitchen. You'll find Mario sitting here, who sells food.
Leave the inn and explore around outside in Gale. There's a woman wandering around in a yellow and brown dress somewhere. This is Carol, who will join your party if you have a high enough reputation. Unfortunately there's a townswoman wearing the same clothes who will demand 100 coins or she'll tell the Mayor that you're there. I wouldn't worry about paying her, since the only thing that happens if you get caught is that you get thrown into a cell which is rather easy to escape from.
If you do get thrown into the cell there's a secret passage in the southeast corner of the room that leads to another room with Zombies. Kill the zombies and take note of the trapdoor in the southwest corner. This leads to the southwest corner outside of Gale. You can either escape the cell this way or, more easily, you can pick the lock. Don't worry, they'll ignore you once you've escaped.
Back outside keep exploring a little bit and you'll find a Nephil beggar. He doesn't give you anything if you give him coins, but be nice.
The second beggar can be found near the southeast corner of town. This is Gelahd, and if you give her some coins she'll tell you a woman you can find in the Herb House who knows something about the Golems.
Just to the northwest of Gelahd is the second inn in Gale, which is run by Cole. Sitting at the bar is Mrurr, who will sell you a boat that will take you to the Isle of Maddok. You want to buy this boat, because it's a good idea to go to the island, since that's the location of the Tower of Zkal.
The block of rooms to the west of this inn is City Hall. In the southwest corner you'll find Commander Leona. Talking to her will get you thrown into the cell as well. To the east of Commander Leona is the Mayor's office. Again, talking to Mayor Rali will get you thrown into the cell. In the southeast corner of the mayor's office is a secret passage leading to a small looping passage and another secret passage. However, going through the second secret passage into the treasury will turn the entire town hostile.
Now make your way to the West Gate and through a door just south of the gate itself. Follow it around all the way to the end in the south, near the docks. There's a secret passage in the northern wall here which will take you to the door to the Gale Library. There's another door between Leona and Rali, but you can't get through it. If you can't pick this lock, wait until you talk to the Herb Seller in the Herb House so you can get the key. Inside the library you will find the location of the Lair of Drakos, the spell Move Mountains Lv.3 and the Heroic Brew recipe.
Now make your way back to the center of town. There are two blocks of buildings, both containing shops. The western block contains Kalen, who provides training; Stern, who sells some really nice Missiles; Velnas, who sells Mage spells and also identifies items; and Nantier. Nantier sells alchemical recipes, but more importantly he'll give you a quest to learn the Heroic Brew recipe from the library. Talk to him a little bit and he'll tell you about a woman who has the key to the library. You need this knowledge to be able to buy the key.
The eastern block of shops contains just two shops, both of which are unlimited item resellers, like Levy in Fort Emergence. The northern shop belongs to Asp. He has some pretty nice weapons in his stock, and, if you give him at least 10 skribbane he'll also show you his special stock, including the Flaming Sword and the Shielding Spike. To the south is Dharas, the armorsmith, who also has some very nice items, including the Crystal Shield.
In the northwest corner of town you'll find a church, which is run by Zachariah. He sells Priest spells and provides healing.
Just to the north of the church is the secret passage which leads to the Herb House. Once you enter the Herb House talk first to the woman near the southern wall. She doesn't tell you her name, but she has the key to the Gale Library, which she'll sell you for 5000 coins. She also sells skribbane.
Now speak to the woman sitting near the northern wall. This is Roeselei, who has some information about a mage living in the mountains to the southeast of Tevrono.
That finishes up Gale, so now lets move onto the Isle of Maddok.