Nay, ‘tis most certain, Iras. Saucy lictors
Will catch at us like strumpets, and scald rhymers
Ballad us out o’tune. The quick comedians
Extemporally will stage us and present
Our Alexandrian revels;
Some squeaking Cleopatra boy my greatness
I'th' posture of a whore.
Whether played by a boy or a woman, Cleopatra is unquestionably a great role. And there are at least a couple of other strong parts for women, most notably Cleopatra's servants, Charmian and Iras. The fourth part is Octavia, Caesar's sister and Antony's second wife (his first dies off-stage as the play begins). It's not a bad part, but small.
I suspect the first thing I will do is increase the size of Cleopatra's female retinue by switching the genders of a couple of characters. There's Alexas, who is officially one of Antony's men, but who spends more time running errands for the Queen. His name won't even have to change. Then there's Mardian, who, as a eunuch, is already half-way to womanhood. Rechristened Mardias, she will be a quieter member of Cleopatra's boisterous clique. I'll have to cut out a couple of eunuch jokes--snip, snip--but I doubt anyone will miss them.
Who else? There is a Soothsayer who appears twice early in the play. Like the Soothsayer in Julius Caesar who says, "Beware the Ides of March," this character is genderless, and could just as easily be an old woman as an old man (who knows? Perhaps they are the same character, always popping up to intone seemingly meaningless but ultimately significant warnings).
That brings the female count up from 4 to 7, at least. Then there's always the possibility of cross-casting some of the soldiers. But it would be nice to maintain a clear gender divide between Egypt and Rome. This is emphasised in the imagery of the play: Rome is cold, sterile, rigid, logical, and violent. Egypt is warm and fertile, teeming with life and colour and emotion. The longer Antony stays in Egypt, the more he feels like he's becoming "womanish." This character transition, although it might be seen as somewhat sexist, is important, and I think it might undermine it a bit to have a bunch of Amazons bouncing around in Rome.
(Forgive my choice of words, but I'm sorry; a woman in a toga is a woman, and no amount of tenser bandaging or penciled-in facial hair will fool an audience with eyes.)