"The Blizzard be strong outside, lads; settle yehself in and breathe the steam; we'll pass the time with a story."
An ancient shrine of a mischievous goddess. The proper offering will give you her blessing, but 'ware you don't feed her wrong!
The PCs are walking along the road, when suddenly a bunch of bandits attacks. The player's dismiss it has just a random encounter, when they find an ornate ring on the leader, obviously out of place with the seemingly poor bandits, who could only afford cheap leather and weapons. This ring has a symbol on it, which, if researched, sets the PCs on a quest. And from then on, the players don't look at random encounters the same way...