I think the Kievan Rus would be an excellent choice for the East and depending on how far east the new map will span you could have the Great Khan for the Horde. Also, who knows, maybe you could try to build the European Union centuries before it had been conceived.
I definitely agree that if you conquer the British Isles, France, and Spain, you are looking at a monster of an empire. I honestly think that if you are able to capture any three major king crowns (England, France, Poland, Spain, Lithuania, Italy, ect.) Then you should be able to declare an empire. Now if you conquer like England, Scotland, and Ireland that's not really an emperor worthy feat. Places like Ireland, Scotland, Denmark, Finland aren't what I'd call major crowns.