Personally I'd go for after Charlemange. More chaotic but with the memory of a short time of unity.

• Holy Roman Empire - I'd need to go over this area again, aside from Charlemagne I muddle the history until much later
  
• Rus - Vikings forging a trading route clear to Constantinople, fighting and allying as they go
  
• Sicily - depending on the year controlled by Byzantium, Saracens, Normans, or some mix
  
• Italy - Lombards, Byzantines, city-states, Normans, etc.
  
• Byzantine Empire - in a golden (gilded?) age; the theme (themata) system is an interesting comparison to the later European feudal system; *the* power at the time, its borders shortened to a stronger more united area
  
• Abbasid Caliphate - esp. their Mamluks; of two worlds and good for intrigue and rebellion & I'm sure they were used against the Khazars
  
• Persia - in flux then ruled by the Samanid Persians, make for a good counterpoint

I'd aim for Sicily as the center, then branch out for adventures. Too close to 1000 and things really change, from England to Persia. Around 900?

Not sure what general sources you're familiar with so apologies if these are not new to you:

• Norman Cantor - The Civilization of the Middle Ages; covers the period nicely including lots of tidbits and people useful for a campaign
  
• John Julius Norwich - has fun narrative books on the Normans in Italy and a history of Byzantium; non-critical but full of juicy detail
  
• Warren Treadgold - far more analysis and numbers than Norwich, very good on politics and miliary matters
  
• Maurice's Strategikon - military strategy, tactics, politics, combined arms, and more, written around 600 and still applies until the aftermath of 1071; IIRC it does predate the formation of the Themata, Leo VI the Wise wrote the Tactica in 903
  
• Osprey Publishing - has several books on the period, the books on Islamic and Byzantium armies of the period in particular are well done considering the thin format
  
• Warhammer Historical - Shieldwall for Vikings etc., At the Golden Gates for Constinapole and surrounding; well illustrated

Sidenote: I hadn't been aware that the Papacy (and by extension Italy) was fairly tolerant of Jews at the time, esp. in comparison to Byzantine lands.

That's a good idea, for Sicily.

I was just thinking of Constantinople itself, since all sorts of people came there. So whether the characters were primitive, nomad, barbarian or civilised, they could meet - thought the primitives would probably be slaves. It's true that certain places changed hands a lot, but over centuries - campaigns last what, a few game years, tops? So you can't get that diversity in time, you have to go for it in a place - if you want diversity.

I've sent out an email asking a dozen or so prospective players this stuff. No doubt some won't reply. Those are the ones who'll be without a game. If you can't even be bothered replying to an email asking you to cherry-pick what you'd like to play, then I can't be bothered GMing you But no doubt, enough will reply with good ideas!

Right, plenty of the four civilization types in Constantinople at the time. And when state policy involves getting your enemies to fight each other you wind up with a lot of allied mercenaries who may be fighting you tomorrow. Or in the army of your rebellious 2nd cousin tonight. Set somewhere between 800-1071 you have a guarded recovery rotting from within.

Italy & Sicily have a lot of differing polities in a small area at the same time. Good as a home for PCs or adventure locales. It wouldn't take that long in game time to go from Constantinople to the Byzantine Exarchate of Ravenna or Catapanate of Italy, a Saracen-controlled port, the Papal State, or through the city-states of Lombardy.

That and I could easily run the Italian area's background events as a simple DBA 5-6 state campaign.

One thing I do like about the Byzantines is their different but not nature. Which should work nicely for your campaign. They're exotic but not *too* much.

Ruleswise:

• Primitives - I'd treat them as those tribal members who've yet to have significant cultural contact with civilized cultures. So a horseman fresh off the steppes, the latest Slavic tribe of the decade, a Pict, a more rustic Rus village militiaman, etc. as well as slaves IMO. In Constantinople to start trade, ally, fight for/against a faction, steal from, on pilgrimage.
  
• Magic - I don't have a good handle on RQ3 magic, but tribal spirits, icons and relics, holy books, and demon & djinn summoning all come to mind.

If you don't already have them take a look at Sandy Peterson's house rules for Runequest 3 (HTML version) including Sorcery, Shamans, and related. Related goodies, including other versions of his house rules are here. He also wrote a good adapation of Empire of the Petal Throne to Runequest for another take on RQ magic. Some of the spells could be used for say Hermetic or Arabic mages.

And a month later, here I am again. I tried a modern semi-realistic campaign but that didn't turn out so well. I think players need there to be a degree of lawlessness, to be able to smash heads occasionally... and so I return to RuneQuest!