Here's a technique I've used. When I invite people to a game I tell them that the game we're playing is a homebrew system called "Valadil's Game" which is loosely based on D&D.
This does a couple things. Firstly, it scares off rules lawyers who want to play RAW. I figure those players aren't compatible with my games anyway and I'd rather just nip that in the bud. It also signals to the players that this isn't another kick down the door, slay the monster, loot the treasure D&D game. It removes that expectation and opens them up to something with more story.
If you want to get technical about it, this is just a restatement of Rule 0. But it works.
It is apparent that you are facing multiple issues here. I will try to address them individually. But first:
Get everyone on the same page
You all evidently have different expectations of play, the game has a few levels of agreement that have to be acceptable to all players, the social contract, and choice of game, and the story of the game are just three examples.
You can use The Same Page Tool - It can help your group discuss and define what you are expecting to get out of the game, an excerpt from the link:
Functional play depends on everyone playing the same game. Sadly, many
people don’t even know or negotiate what that means, and a lot of game
texts leave crucial things out. Too often, people come with different
ideas and don’t realize it, and it turns into a mess during play.
So, this tool is designed to clear that all up before you start
playing.
After you have figured out what your expectations are - you can start thinking about what world to play your game in. There are a few options available to make it so that anyone could GM those worlds.
1. Choose a world you all know.
Choosing a world you all know (like Middle Earth, or Narnia, or even a historical period) is pretty straightforward, but you should make sure that everyone has about the same level of knowledge about that world, or that it is easily accessible.
2. Create a world together.
You can do this on your own - or you can use a cool minigame designed just for this like Dawn of Worlds which puts everyone in the role of a god-like creator taking turns designing and building a world and giving it a basic history, excerpt:
It was the product of many minds playing off one-another over the
centuries. The solution to our dilemma seemed only natural, we would
create a world together. Everyone would have a hand in it, everyone
would know its history.
We would become the gods of our own fantasy world. We would raise it
up from the meager foundations of stone and water. We would raise up
great civilizations, set them at war, guide them in science and magic,
and give them leaders. And we would do it in about six hours. From
this singular idea arose the game which you now see before you.
Once you have that - the decision of who will be the GM is something that I can propose two methods for, but I am sure others exist.
1. Choose a GM each session, and every player also has a PC
In this manner, the GM role is a "hot seat" players taking turns playing the GM and their own characters the rest of the time. This is a bit tricky if you are doing long campaigns, but for sessions of a few hours with smaller adventures this could be really fun.
2. Take turns running adventures in the same story
Every GM will play out their adventures and then switch out with another player at the end. You could also keep the PC's stories perpetual, just switching out one character and adding another they might meet on their travels - this keeps the players vested in their characters and also provides for some interesting stories.
Best Answer
Play by mail mechanics vary immensely, to the point where there are probably as many possibilities for rules in PBEMs as there are in tabletop pen and paper RPGs. Some games use pen and paper rules sets, some use board games, others custom PBEM rules (or programs) and some no (mechanics) rules at all.
What I have found from my experiences in both playing and running PBEMs is that there are three general "styles" of PBEM that dictate how rules, resolution and interaction are handled between players and the game environment.
One important, immediate thing to realise is that in PBEMs, personal (small unit) tactical combat using dice resolution for every action is generally very, very rare. It's slow, tedious and annoying to (for example) try and run a D&D 3.5 combat through email; it is not what this type of game is about.
That said, I'll break down your questions for each game style.
1. Tactical PBEM
A tactical PBEM consists of a game where players submit a series of orders (usually on a simultaneous deadline, but they can be on a round-robin basis as well). The GM then makes any rolls/checks/etc. required to determine the outcome and sends out results to the player(s) involved. These games tend towards more tactical and management styles of games.
Email replies for this style of game are usually personal and contain information that would be "of use to the enemy."
How is this style actually played?
Players submit a series of orders. Such as "Move unit 6 north six miles, engage any enemies" or "Week one attempt to join the East Anglian Regiment, Week two if I am in a regiment train, if not carouse."
How should players describe their action, in a way that does not mess with the story?
Story in these games tends to happen in part by resolution from the GM, but also between turns via public forum, email, etc. among the players in a way that will not contradict order results; i.e., players provide as much fluff as they want (and it can be a lot). The golden rule for this style of game is "don't interact in a way that will contract any possible actions." – You can't say, "I'm in the Anglian regiment now," if your order to join it hasn't been resolved either way yet.
How is an action resolved?
The GM will resolve all orders for this style of game, sometimes using a program to manage the orders automatically and spit out the results sheets.
Importantly, how does someone GM something like this?
This is a reasonably easy type of PBEM to manage mechanically as all orders are well defined and interactions have black and white results (as long as the rules set holds up!). As mentioned there are even programs to do this, to the point where the GM can just collect the orders and stuff them into a program to resolve it all for them. Manual mechanical systems however can take a lot of time for a GM to resolve.
What examples are there of this?
En-Garde, Diplomacy, It's A Crime. There was even a version of UFO: Enemy Unknown that ran via email. Stars is an example of a program-run PBEM.
Note that although these games are generally tactical/management heavy they can generate a lot of fluff. Message boards and email lists are usually set up for this sort of game where players can interact, describe events, tell stories about their realm/character/corporation, make threats, etc., entirely irrespective of the actual game turns – and as results arrive they can react to them.
2. Narrative driven PBEM
These sorts of PBEM usually have no mechanics rules at all and typically focus on a single character per player. They are virtually interactive/freeform stories. The game rules generally boil down to three crucial laws for the game world.
These games are story based games and entirely fluff driven; players in the game write stories about their characters in the setting provided and managed by the GM. The players typically have control only of their own character. Where two characters interact, players either communicate directly via email to determine resolution and agree on something or try to predict the responses from the other player and leave placeholders in their stories so that the other players can respond from their character, subject to law #2.
Email replies in this game are usually to an open forum or mailing list so everyone can follow what is going on. Character sheets for this style of game may have no mechanics or statistics at all on them (and indeed usually don't), just description and background.
How is this style actually played?
Players write stories and describe what their characters are doing. Enjoyment comes from crafting a well written saga rather than slaying 200 billion orcs. Usual focus is on character development. An example slice might be:
The stories and replies are usually somewhat more expanded than this! Note that the GM may not even interact with players once they get going and this can be ideal; two (or more) characters follow off on a thread together on an epic quest and create a story together.
How should players describe their action, in a way that does not mess with the story?
This is the trickiest element of this style of game; it involves either predicting how someone will react or communicating personally with them and determining what will happen. The GM controls the world and the NPCs (although players can help) and will guide events (through descriptive messages).
How is an action resolved?
By agreement. Players in this style of game must be flexible and willing to make an interesting story and not want to "win" all the time; indeed winning becomes exceedingly boring in these games. The trials, failures and struggles that lead to character development are what is important. When characters "fight" then they both need to be willing to give/lose something in such an activity or they are not going to have fun – and more importantly no-one is going to what to play with you if you always kill your enemies. Death is not a common character occurrence at all. Think soap opera.
Importantly, how does someone GM something like this?
GMs provide the flavour, the big events, the big bads; they are like a director in a movie that provides details of the approaching army, the details of the plague that is sweeping the land, the earthquakes that shake the city. They also manage important NPCs. This can be a lot of work, but they also get to write a lot of story. The hardest thing for GMs is managing players who do not understand that this sort of game is a cooperative effort rather than a personal ego trip; such players need to shape up or ship out.
What examples are there of this?
Absolutely anything can be made; existing book/film/game genres are very common choices (Mass Effect, Star Trek, Conan the Barbarian, etc.) so that new players are aware of the setting. It can be a GM-made world of course, but this requires a lot more reading for the player and tend to be harder to get started in. Star Trek PBEMs in this genre are one of the most common.
Games of this style can end up being very much like play by post games (i.e., forum games) but at a slower speed. i.e., instead of determining what happens via email or trying to guess a response, the players simply stop the story and tag the character (or GM) they're interacting with to continue the story.
3. Downtime PBEM
This sort of game is usually an in-betweener or more a "high level" facet of an another ongoing campaign. An established rule system is used (AD&D, Rolemaster, whatever) and the players describe what they want to do. Combat can occur, but it is usually avoided as the players in this are looking for more management and personal interaction.
Email replies for this sort of game are typically personal, but aspects of what is happening are usually broadcast around on a mailing list. e.g., "All hail! the King declares that the grand Sir Eric has been made a Knight of the Order of the Rose." And so on.
How is this style actually played?
This style is the most varied, since it can be as little as a means to keep a tabletop game going while players are away. Typically players will describe what they want to get up to (in varying amounts of detail, from simple one liners to many paragraphs) and then the GM replies with what's going on.
How should players describe their action, in a way that does not mess with the story?
This is a "what you put in is what you get out" style of game; players who use short descriptions and don't like story will find this boring. The GM will sometimes have to reign in players who make assumptions about what happens and have their characters try to do too much.
How is an action resolved?
Action is resolved using the game system used in the main game; combat can be tricky but this is usually resolved either in a short real-time online session between the player and GM or with a few rolls by the GM.
Importantly, how does someone GM something like this?
This depends a lot on how much the players put into the game; the rules system is your bible and constraint for managing the players. Events can continue but the important thing is to avoid combat as much as possible so that character development can continue. In the end it's a lot like a tabletop session, but with the focus on development rather than hitting stuff.
What examples are there of this?
Almost any pen and paper RPG can be adapted for this. Some are more suitable than others; generally games that focus on the tactical aspects of a character's ability (such as D&D 4e) are less suitable than ones that describe a character's persona and abilities (such as Fate).
TLDR
PBEMs vary immensely. There are three general styles: Tactical, Narrative, and Downtime. Combat is a rare affair in the latter two, which generally concentrate on fluff. Tactical games tend to focus on larger-scale management and combat between units.