Cordoba:
It is the year 711. You can hardly believe your luck. The stupid followers of the deposed Visiogothic king Womba actually invited you and your fellow muslims over the straits of Gibraltar. With the reigning Visiogothic king Rod defeated through trechary, it was an easy matter to seize full control with the help of the persecuted jews. Now you can build a rich and happy Caliphate, full of poetry, art and religious toleration!
Arabs:
"It is the year 635. The prophet Muhammed, peace be upon him, accomplished what no one thought was possible - uniting the tribes of Arabia. You, Abu Bakr, has been chosen to succeed him as Caliph and expand the House of Islam. After a devastating war with Sassanid Persia and raging religious controversies between Chalcedonians and Monophysities, the land of the Byzantine Empire is ripe for conquest. There will be many centuries to build up your forces before the western crusaders cast their gaze towards al-Quds"
Note: Do we want to include the warning about the crusader attacks for the Arabs? If so, should we call it al-Quds or Jerusalem?
Venice:
"It is the year 810. Fleeing the onslaught of the barbarian Lombards, your people and the remnants of the Byzantine Exarchate of Ravenna have settled on the inaccessible islands in the lagoon. The recent agreement between Charlemange of the Franks and emperor Nicephorus in Constantinople means that you will be left alone for the time being. There has never been a better opportunity to build a rich trading empire that will dominate the seas!"
Norse:
"It is the year 780. The winters in Scandinavia are harsh, but have bred a sturdy people and your longships are the envy of any sailor. Now, far away Vinland, the coast of Normandy and the rich monastery of Lindisfarne beckons. Be bold, be swift, be strong, and the halls of Valhalla will await you!"
Bulgaria:
"It is the year 680. After the catastrophic defeat inflicted by the Khazars, you and 50 000 followers have fled from Old Great Bulgaria north of the Black Sea. After smashing a Byzantine army in the battle of Ongal in the Danube delta, they have been forced to recognise the Bulgarian Empire. Never again shall the Bulgars be forced from their homes!"
Germans:
"It is the year 858. The great Frankish inheritance have irrevocably been split into three, with the eastern part going to you. As the Byzantine Empress Irene rejected Charlemange's marriage proposal, you should instead build a Holy Roman Empire for yourself!"