The best way to find new map areas is to leave every map by every screen edge you can leave from. Just going to the map screen and clicking back on the map location you just left from takes no time, reveals map connections in that direction, and takes you back to the same point you left from.
As for Gullykin and Firewine, I think I uncovered them when I was doing the Nashkel Mine quests, so poke around there and something might come up. Someone else will know better don't worry.
If you dont have anything against guides, this one is absolutely amazing. It does have spoilers, and if you dont like guides obviously dont read it ;D http://www.forgottenwars.com/bg1/
Comments
As for Gullykin and Firewine, I think I uncovered them when I was doing the Nashkel Mine quests, so poke around there and something might come up. Someone else will know better don't worry.
http://www.forgottenwars.com/bg1/
This being the internet and 2013 and stuff...