Rules are made to be broken
This is the mantra to always keep in mind when engaging the Fate series.
By default—the "rule"—servants are summoned with their body as in their prime (physical prime normally, though servants renowned for more mental deeds would be in their mental prime, which could be quite a good deal older). Except when they aren't.
Leonard Da Vinci could be summoned in the appearance of the Mona Lisa, both because that is the mental image people most often immediately associate with Da Vinci (even though they know they're distinct people), and because Da Vinci himself wanted to.
Penthesilea may have died so incensed by Achilles seeing her as a woman rather than a warrior even on the battlefield that she intentionally manifests as a child version of herself, hoping to make it impossible to suffer such an indignity again.
Napoleon can be summoned as a tall, manly bro if he is summoned more for the concepts he represents (achieving the impossible, responding to the wishes of the people, etc.) than anything else.
So the rule can be subverted by legends and history providing many alternatives for what their appearance and prime are, as well as the very will of the spirit itself. The spirits are enticed there with the promise of a wish on the grail, but the spirit ultimately influences how they manifest in order to best pursue their goal (whether it's the wish on the grail, or simply a chance to fight honorably against other heroes, or whatever else).
Heroes are not (always) one-dimensional
Any servant is just a distilled interpretation of the sum total of their history and legends. The servant Classes are just limited vessels the spirit is shoehorned into.
While Hercules may have legends about his archery skills (including arrows dipped in Hydra blood/poison), when summoned as a Berserker the archery aspects do/can get filtered out as irrelevant. And Cu Chulainn may have some limited rune capabilities as a lancer, but their full capacity is drawn out only if he is summoned as a Caster.
As the last example points out, the form and nature of a servant is also influenced by the class they are summoned into, which is in turn related to the summoner. With no catalyst, the grail attempts (another rule, here) to summon a hero that is similar to its summoner, in order to assist their cooperation. With a catalyst, it attempts to pick a version of the hero that is, again, similar to its summoner, though this may be harder to achieve.
The latter is the case with the Saber and her summoner from Fate/Zero. The summoner would have infinitely preferred an Assassin, as that suited his personality and style better, but his catalyst pretty much forced a Saber that was intensely dedicated to open and honorable combat.
Gilles de Rais might also be a soldier, as when he served Jeanne d'Arc or a horrifying occultist. His history and legends include both tales of a competent solider and strategist, as well as that of a child-sacrificing occultist driven mad by Jeanne's death. Which one you get depends on the situation and the summoner (if any).
History can be inaccurate or ambiguous
When a gender swap (from our perspective) happens with a character, a common explanation is that the historical record simply got it wrong. Francis Drake is a guy, right? Nope, she's actually a beautiful woman with giant bazongas; we just remember it wrong. Other heroes may have ambiguous gender (and/or sexuality) in their histories, which may allow them to be summoned in a seeming gender-swap. Just try to figure out what Astolfo or Chevalier d'Eon are without cheating.
As women frequently occupied a notably inferior position in the social order for much of history throughout much of the world, this creates a strong incentive for ambitious and adventurous women to mask themselves as men in order to realize their goals and dreams. Assassins may have benefited from a certain amount of gender fluidity, as being able to pass for men or women would make it easier to slip through vulnerabilities to reach their targets. Even some historical generals and warriors have records drawing into question their gender. Did they never have children or much interest in women because they just weren't that sexual, and were singularly focused on their duties? Or perhaps they were actually a woman?
In the case of King Arthur (the Fate version of which was originally known as Artoria, but has more recently been changed to be named Altria), in the FSN story/explanation her true identity was masked and known only to a few. She was kept at a distance or in a heavily masking helm when visible to the public. Other public appearances were often done by Gawain or another Knight-in-the-know, borrowing Excalibur if necessary to really sell it. The average citizen would have few to no opportunities to see the King anyway. And in this setting Arthur is noted (and at times criticized) for being an extremely distant, removed, and unemotional ruler: this was the behavior of the ideal King that she envisioned. The King's aging was also stopped the moment she pulled out the sword in the stone, permanently leaving her as an androgynous/tomboyish 14 year old (I think materials may now be saying 16, instead).
King Arthur herself was so dedicated to maintaining the deception and being the ideal King that she developed body image issues, supposing herself to be muscled and un-woman like when the protagonist actually succeeds in developing a romantic connection, despite her obviously waif-like appearance and porcelain skin. She had the heart of the dragon and superhuman strength as a result, which may have encouraged herself to see herself this way. And the conflicts caused by her true gender motivates many other story points in Arthurian legend: why there is a faction of rebels that Mordred can join (not everyone likes a cold and distant king, but she must be so to maintain the ruse, or so she thinks), why Mordred even wants to rebel, why Guinevere and Lancelot hook up (Guinevere was not a lesbian or bisexual, and she had needs; Arthur intentionally overlooks their relationship, until it becomes public knowledge, out of guilt for how difficult their marriage was for Guinevere, and punishes Lancelot only out of a sense of Kingly necessity rather than any actual feelings of betrayal), etc.
Iskandar also falls into this, as Iskandar himself explains the basis for supposing he was short is because he was compared to even more gigantic figures. In particular he says the historical accounts say he was dwarfed by the throne of Darius because Darius himself was a giant among men, who truly did make the beefy Iskandar look short and puny in comparison.
It's a multiverse (and then some)
The Fate universe, or more broadly the Nasuverse, is a multiverse setting in rather the most expansive sense. Multiple universes, alternative histories, time travel shenanigans, etc. are all available. One story in the Nasuverse may be incompatible with others for any number of reasons; a character in one may simply not exist in the other. In particular, every single storyline that occurs in a game like Fate/Stay night—including bad endings, not just the normal/true endings—are canonically true and all happened, just across a variety of timelines/worlds.
Moreover, the Throne of Heroes, where the Heroic spirits reside and are summoned from, sits outside of time and the world, and has access to all of these alternative timelines etc. So heroes have a multitude of possibilities available to them, not all of which need to have been realized within the world and timeline their spirit is summoned into.
The prototypical example is a certain FSN servant who comes from the future of a timeline that is not covered by any of the routes or endings of the FSN game itself (and has never been fully detailed).
Out of universe rationales
The out of universe rationale for gender swaps and appearance changes is the same one as usual: making money. It was determined that a Female main character with a Male Servant wouldn't sell as well as a Male main character with a Female Servant. So once that was settled on the easiest thing to do was to just swap the genders, and so bam, female King Arthur is born. Other characters had their appearances changed to fit modern perceptions of what an archetype should look like. The vainglorious, obscenely wealthy, painfully arrogant king should be more of a pretty-boy, with golden hair to reflect his wealth (gold); not the rough-and-tumble manly warrior that Gilgamesh perhaps ought to have really looked like. The ultimately in manly, world-conquering, modern bro-dom should be huge and muscled and gruff, his intrinsically intimidating physique contrasted with how amiable and bro-like he behaves; not the rather more effeminate physique that Alexander the Great should have had.