Firstly, Altria. what we see in Fate/Stay Night is not originally what Kinoko Nasu first wrote, the original version was called Old Fate (旧Fate) or Fate Origin which was re-imagined into Fate/Prototype, in this Altria's character would have been a man (Arthur) and Shirou's character would be female (Ayaka Sajyou). Of course, this is no longer part of the Canon that is the Nasuverse but I thought I point out that originally Altria would have been a man.
As for Altria herself being a woman, Merlin's prophecy never indicated the gender of the future king, it was just a common view that a King would be a man; the inscription on Excalibur (or Caliburn, I can't remember which it was) also didn't indicate that a man had to be the one to pull the sword out.
As Altria acted the part of the king, she dressed and acted much like one, even to the point that Merlin made her into a pseudo-male and Mordred's identity was concealed, so because of that, their genders are normally concealed and were thought to be men. There is also ambiguity with the Arthurian Legend as in the Visual Novel, Shirou says that some legends portrayed "Arthur" as a woman or a group of people, which is why he wasn't surprised that "Arthur" was a woman (more so that he summoned her).
Also, "King Arthur" became more of a symbol than anything else. Merlin was clearly aware of this when he warned Altria before she pulled the sword from the stone that if she did she wouldn't be human anymore.
One thing you may have missed is that Altria isn't in the Throne of Heroes like most heroic spirits. Those who are in the Throne of Heroes are in there because they made a contract with the world to receive the strength to be a hero so it's their price. Altria became a hero on her own, but on her death. She desired the Holy Grail to redo the sword-drawing Ceremony and find someone whom she believed to be more capable of being a king than her. She made a contract with the world to become a heroic spirit if she got it. Therefore, while Servants like Iskander or Gilgamesh who are copies with their original still at the Throne of Heroes, Altria is always herself. This is why she can remember the events between wars when normally even if a heroic spirit is summoned again they won't remember any other wars they were in.
Now, let us move on to Heroic Spirit EMIYA, who is a Counter Guardian. Before I begin, I should point out Altria is not a Counter Guardian. Counter Guardians are a special group within Heroic Spirits who made a contract with Alaya and as such they are incorporated as part of humanity’s Counter Force summoned whenever a factor in the extinction of mankind is detected.
Regarding EMIYA's summoning, he is summoned from another reality which is entirely possible for the Holy Grail. One of the key things in the Nasuverse is that there are alternate timelines which are all still Canon because of the Second Magic which is the Operation of Parallel Worlds. The 5th Magic's Domain is unknown but it's abilities are related to Time Travel. However, Touko Aozaki claims there should be more to it because time travel is also governed by the Second Magic. Kischur Zelretch Schweinorg who wields the 2nd Magic was actually present when the Holy Grail System was first created, so being able to get Heroes and the such from other times and realities would then be possible if it incorporated principles of the 2nd Magic (which I would do in order to crystallizes a Servant's feats in the from of the Nobel Phantasm).
Now in EMIYA's timeline, the 5th Holy Grail war was a disaster:
In Heaven's Feel route in the visual novel, Archer recognized Sakura's Shadow and how it was attributed to Angra Mainyu. Whether it acted during his 5th Holy Grail War is unknown but it is clear that Angra Mainyu and the Greater Holy Grail was not destroyed/shut down before a major disaster occurred.
If EMIYA came from the same reality that Fate/Stay Night was in, then he would have known that he would have not been able to kill himself and by killing himself he may have caused more destruction. Practically, Fate/Stay Night occurs in a separate timeline/reality to the one EMIYA existed and the Grail summoned him because of Rin's Pendent which he still kept. So if EMIYA's strength comes from how popular his legend is, then it will be unaffected because his Legend is from a separate reality which will still be known.
Also Rin is shown to be able to draw Mana from other realities in Heaven's Feel by using an implantation of the 2nd Magic
Now I haven't read all too much into Iskander so I can't vouch for the difference with his legend. However, this could be explained because the Holy Grail System is damaged. Rather that rehashing what caused it because it could be spoilers, you can read the 3rd and 4th Paragraphs here to read up on the discrepancies with the Servant Summons or look up on the wiki on how the system was originally created. However, since Mordred's legend is unaltered in Fate/Apocrypha, and in that timeline the Einzbern's summoned Ruler rather than Avenger, we can safely say that Altria wasn't altered when being summoned.