Fallout 1 and 2 deserve a lot of praise in this regard. In both there's a big main quest, and in both there's a vast array of side-quests in most locations. What's special is that not only does everywhere have their own mini-stories but to what extent it helps your own greater personal quest is very well handled. Sometimes you'll get your regular quest rewards and stuff, but absolutely nothing that helps with the main quest. Sometimes you'll get a hint on where to look. Sometimes you'll get something really important (though you might not know this until later). I'm failing to explain it well but basically it's all really well and believably handled with a great mix of tying into your main quest in a variety of ways.