I've posted about the 13th Age Icons before. I've even pulled together a list of possible Icons for Numenera since the mechanic is pretty easy to graft onto other systems. I'll leave those posts and the 13th Age SRD (found here or here or even here) to explain how to use Icons rather than repeat myself. Instead, what follows will be a discussion of some of the notable NPCs who may hold enough power and influence in the lands of Rûl. Some of these may not be suitable for every game, but since a given group of players will probably not all choose different Icons your group can probably help you weed out the chaff. It also should go without saying (but this being the internet I'll say it anyways) that these are my interpretations and opinions on these characters. I interpreted what was in the book as best I can and added to it in a way that I felt made sense for the setting and the narrative that we have seen. Your milage may vary, but I do welcome constructive criticism.
That all out of the way let's get into it...
The Orc King
For the core setting it is hard to deny the Orc King as an Icon. The leader of the orc revolt and the slayer of the Emperor the Orc King has rewritten the political landscape of Rûl through is actions. Little is known about his motivations in the current times but it is safe to say that the Heir and the Orc King will be mutual antagonists.
The Emperor (deceased)
If you want to play in a historical game, or if you have characters who are older the Emperor may still have some sway. The Emperor counted the Archmage, the Heir, and the Governor of the North as allies and vassals in life. Likewise the King of Sails, the Sea Lord, the Hand of the Demon, and the King in Stone were counted as enemies. In death some of these may still be friendly or antagonistic to those who still revere or carry out the posthumous will of the Emperor.
The Heir (Horus of Tear)
The second son of the now deceased Emperor, Horus now finds himself the Heir to a devastated empire. Sent to rule over the lands of Tear Horus has proved his worth and changed his fortune from a wastrel to a capable leader. With his father and elder brother dead in the orc uprising Horus finds himself with all the reason in the world to return to Caercas, though not to continue his indolent ways as before but to reclaim the empire for his family. It remains to be see if he will move against the Orc King, or who his allies are, if indeed he can claim any of those loyal to the broken Empire as allies.
For years the Archmage served the Emperor, even going as far as to create the Orcs to serve as the Empire's troops. Since the Orc uprising the Archmage, and indeed all of the imperial mages, have been strangely silent, almost absent from the Tower Arcane above Caercas. It is unknown if the mages have abandoned the Tower, allied with the Orcs, or if some other event has befallen them. Their current motivations are a mystery, but their agents throughout the world will still serve until it becomes clear that their masters are gone.
The leader of the Cult of the New God's faithful and the leader of the Holy Kingdom, the Matriarch has tens of thousands of devoted followers within the bounds of the empire. Like the Archmage the Matriarch was a vassal of the Emperor, and in the wake of his death the Matriarch is poised to ensure the smooth continuance of people's spiritual lives despite the political upheaval that threatens their mortal well being. To this end the Matriarch and her faith wage a never ending war against the dark forces of the world. Most prominent of this are the followers of the Demon Lord, especially the Hand of the Demon. Second to that the faith continues to press for conversion of those who still cling to the heathen ways of the Old Faith.
The Governor of the North
The Governor was a vassal to the Emperor before the uprising of the orcs; now the Governor is in a position to potentially carve out his own kingdom from the Northern Reach. The Heir will probably oppose such "treasonous" actions if he seeks to become the new Emperor, alternately he may become a staunch ally if the Heir contents himself with Tear. The Governor's main enmities will come from the King in Stone and the Betrayer who will both seek to regain or take parts of the Reach.
The Queen of Summer
Reigning over the declining fae the Queen of Summer has pulled her people away from human lands to Alfhiem and the Lands of Summer. Despite this her people continue to touch on human lands, stealing children and leaving behind changelings, or capturing mortal men and women away as lovers before tossing them away when their fancy fades. The Summer Queen's primary antagonism rests with the Betrayer, and his folk.
The Betrayer (Dark Fae)
Former Prince of Summer, son of the Faery Queen, the Betrayer and his followers broke from the Queen and stayed in the mortal realm to war against the invading Edene people from across the Auroral Ocean. That act turned the Betrayer and his kind down a dark path creating murderous fae like the Redcaps and Boggarts. The Betrayer and his folk despise what the invaders have wrought in their homeland. The empire and its people are as much their enemies as the trolls and undead. but the precocious fae occasionally take a person or village under their wing when it suits their purposes as well.
The Dark Lady (Kingdom of Skulls)
The horror that rules the Kingdom of Skulls, the Dark Lady is both a child of now destroyed Gog and the lover of the now deceased Witch-King. Hatred for the Empire has settled deep in the Dark Lady's bones for the losses she has suffered. Her flight to the ice cold lands of the deep south has frozen that hatred, and the loss of her two sons shaped it into a dagger. The Dark Lady watches the chaos is tearing at the Empire and plans her revenge against the people who ruined her life. With the undead thralls who were her sons at her side the Dark Lady may not even realize that she serves the Demon Lord through her actions.
The Sea Lord
Ruler, such as it is, of the Pirate Isles, the Sea Lord and his fellow prey upon the Kingdom of Sails, and the ships of all other nations. The Sea Lord is not likely to stand with any other Icon, and is possibly an enemy to all as his forces prey on any ship that sails the seas laden with gold and goods.
Alternately if you choose to drop the Freeport campaign setting into Shadow of the Demon Lord (like I did) the Sea Lord represents the ruler of the city which is probably added to the Pirate Isles. In this incarnation the Sea Lord is more of a mercenary neutrally aligned figure who sees to the wealth of Freeport by allying with whatever nations can pay the price for Freeports fleets, and the merchant guilds who use Freeport as a hub of trade and shipping.
The King of Sails
The Kingdom of Sails has remained largely free of the influence of the Empire. Being a kingdom of islands with a superior navy has enabled them to fend off the empire while maintaining a strong presence as an economic power through trade. The current king is a gluttonous lecher who is currently more interested in his own hedonistic pursuits than he is with ruling his kingdom. The Sea Lord is likely to take advantage of this weak ruler at some point and expand the influence of the Pirate Isles, while the other kingdoms will likely find themselves unable to gain any help, economic or otherwise, from the the Kingdom of Sails during the coming strife.
The King in Stone (Dwarf King of High Stone)
The dwarfs have lived in deep stone throughout Rûl for time immemorial. The dwarfs of High Stone have warred against the fae, the first people, and later the Edene. In their way they see enemies in all their neighbors, and their long lives mean that they carry grudges more easily than many. The King in Stone sits on his throne and plots to expand his people's kingdom, a conflict sure to bring him to war with the Governor of the North.
The Hand of the Demon
The Demon Lord reaches out to Rûl and gives power to many followers. Though those followers may be discarded as casually as they are empowered there will always be one who holds the greatest favor of the Demon Lord and from him great power, and the alliance of horrific demons. The Hand may be ally or enemy of any of the other Icons depending on their current plan to sow darkness and discord in the Demon Lord's name. Likewise the position may change hands (pardon the pun, but I had to) at a moment's notice as the Demon Lord's favor finds a new worshipper.