I think a Roman Empire-esque type realm is fairly common in many realms, complete with Emperor/Prime Minister and Senate, etc. Mostly these are Republican or Democratic realms who have carved out large empires for themselves. The Cagilan Empire comes immediately to mind, though I know little of their actual internal atmosphere/culture.
The various Pirate realms are interesting as well, and probably not exactly "medieval" so much as 17th and 18th century-based. Madina comes to mind, and I think there used to be one on the Far East out of Batesoar.
I don't know of any Asian or African themed realms, though that could be pretty cool if done and thought out well.
