You cannot exile Progenitus or True-Name Nemesis.
"Protection from everything" has a specific meaning in the rules:
702.16j “Protection from everything” is a variant of the protection ability. A permanent with protection from everything has protection from each object regardless of that object’s characteristic values. Such a permanent can’t be targeted by spells or abilities, enchanted by Auras, equipped by Equipment, fortified by Fortifications, or blocked by creatures, and all damage that would be dealt to it is prevented.
So nothing at all can target Progenitus.
"Protection from [a player] also is specifically defined:
702.16k “Protection from [a player]” is a variant of the protection ability. A permanent with protection from a specific player has protection from each object the player controls and protection from each object the player owns not controlled by another player, regardless of that object’s characteristic values. Such a permanent can’t be targeted by spells or abilities the player controls, enchanted by Auras the player controls, equipped by Equipment the player controls, fortified by Fortifications the player controls, or blocked by creatures the player controls, and all damage that would be dealt to it by sources controlled by the player or owned by the player but not controlled by another player is prevented.
Whether created by an emblem or not; the controller of the emblem is the controller of the triggered ability; so it cannot target True-Name Nemesis if that player was chosen.