People met on the road, (random or otherwise), I have found to be great sources of plot and fleshing-out material for the world. An encounter might begin with hearing sounds of a fight round the next corner. On rushing up, the players find a merchant's caravan under attack. If they help, they will have a useful contact who is probably well-disposed to try and reward them. If travel is dangerous in your world, then locals on the move will be hoping to team up with a well-armed party. This can get players away from the inevitable inns as plot starters. Eg. " Well we are finally back in Jardor - these villages don't change much." " Same rotten-looking inn - lets see go chat up our good merchant Waller instead and see if we can con a free meal and board" GM - you go to Waller's house. " My friends! Newly arrived back in these parts? Come in, come in -I'll get the servants to send us some refreshments suitable for the travel weary. - Oh, I would like you to meet the Lady Damier - we have just been discussing a certain difficulty of her's, haven't we my dear. These good folk might be just the people you need ... " etc etc.
When players get used to meeting fellow travellers on the road, then some not so random ones can be throw in. Eg., a thief on the run; a mage burdened with some powerful artefact that he/she cant properly control; a dying messenger etc. A couple of good ones though are: 1 - THE SPY - so how do your good role players feel about king and country? They meet with what appears to be a foreign merchant riding a single wagon, along with his cook, apprentice and a mule skinner. In reality he is a spy, sounding out local opinion on the rulers, gathering information on defences and paying off his collection of local spooks. A false bottom in his wagon will be full of money for the payoffs and bribes. The meeting will be on a wilder stretch of road, and he will suggest the party travel with him - even offering to pay. If the players are in their own country, he will be interested in their opinions of the ruler (your players have some? :-) ) and will be telling various scandalous and completely untrue stories about them. If they are also foreigners, he will be asking after any military information they may have gathered in their travels, in a roundabout way. A lovely role for the GM. You need plenty of events to create the GM-player dialogue. Here are some suspicious ones that will help the players. Attack - the wagon IS attacked. All of the spies party, even the cook, reveal themselves to be very competent fighters needing little protection. They may use some fairly rare and difficult weapons too. Visitors - by day another well-armed man of same nationality will ride up (actually he is part of the same party). He will be taken aback a little by the party's presence as he has important news of a hidden defensive fort near a ford to impart. The spy will pretend he doesn't know him but hail him as a fellow-countryman, bidding him drink a toast in the wagon and share news of home. Players will need some special listening skill and the language to hear what they say. On leaving, he will nearly ride into the cook and they will curse each other by NAME, despite never having been introduced. At night, a watching party member might notice one of the spy's paid spooks, ( a scruffy local peasant ) creep into the camp to collect his pay and warn the spy of an army patrol. If the players confront the spy over this, he will say the man is a blackmailer, knowing of an unfortunate deal with a local lord and demanding money not to tell the lord he is back.
If the players start getting obviously suspicious, the "merchant" will suggest the road is safe now and they ride on unencumbered by him. If they still stick around, he will sabotage his own wheel and beg the players ride to the nearest village and send back a wheelwright. "Continue on then, don't worry about me." If the characters leave but then watch from hiding, they will see the armed horseman return and the "merchant" will trade clothes and places with him, allowing the spy to continue overland while the others see to the wheel.
The spy scenario could be a prelude to the invasion plot, described in "We Go to War"
2- THE UNWILLING BRIDE - a flash outfit of two coach/wagons led by an austere old noblewomen will beg the party help protect them. She will tell them they are taking a bride to her wedding in a nearby (about 2 days away) town and their escort has unexpectedly had to pursue a known rogue with his cronies, who tried to waylay them. The woman is the bride's guardian aunt (she is an orphan) and the wedding is an arranged one to another powerful family for mutual control of the bride's estate, enriching both families at the bride's expense. The "known rogue" was her real love (perhaps a Romeo from a despised rival family?) trying to deliver her. The party also consists of several grooms, maidservants, an aged valet (on the brides side in any encounter - he is loyal to her parents memory) and two dour men-at-arms. The bride is desperate and while she will be unable to appeal directly to the party, the valet will be her messenger and tell them of her plight. While finding a way to spring the bride and reunite her with her Romeo shouldn't prove too difficult for the party, this plot should deal a mass of consequences to the party. They will have gained some very loyal friends but contracted two influential families of enemies. The region should become very hot for the party with wonderful potential for a vendetta.