I'd suggest some units/ hero and a lil story for ya :
Units :
Sand Worm : I saw a great one at thehelper, looks incredibly cool
Sand Larva : Maybe the larva has to grow before becoming a sand worm
Hero :
Lord Of The Desert : A sort of sand elemental that wields a stone sword, moves like a tornado, would be cool if he was the main bad guy
Story : Karr, year 156. There was a group of travellers, all masked in black that were crossing the terrible cursed desert of Shahat. The nomad tribes who lived in the desert didn't dare to aproach them, because for the nomads called Humtwuk, black was the symbol of hell.*There are many divisions in the
Humtwuk, those who control the underground rivers with their magic are called the Humtwar, those who are extremely advanced in technology are the Humtwech and those who are one with nature are the Humtwiz*
Suddenly, 20 mysterious forms emerge from the sand, *SAND WORMS

* and engage in a ruthless battle with the monsters. Those beasts were still young so they soon fell to the blades of the travellers. Taking a certain time to recover from the exhausting battle, a tornado soon comes towards them. The tornado slowly becomes the form of a sand elemental who tells them :
-Fools! You dare attack the lord of the Shahat Desert's minions?!
The leader of the travellers laughs and says in an unknown language :
-Nige Howe Swe
Soon after, the elemental desintegrates with a horrible yell, but it is impossible to kill the invincible demon as he comes back in the form of an abomination and he says, still recovering from the blow of the man :
-You, you are a Tigerian...
As a response, the man laughs at him again. The spirit, furious, says :
-Very well young Half God, you leave me no choice...
The lord of the desert disapears into the sand before reappearing next to the only women of the group, who was holding a baby with her, and slams her with a wave of sand, a sound of cracking bones and blood spilling everywhere
was heard. The demon soon appears with the baby still alive in his hands as he laughs maniacally, saying :
-This is your child huh Tigerian? Only if you bow to me that i will give you your child.
The demon then disappears, while the man angrily yells out all his anger and sadness...
*Ok, so this story is about the father, NAME, finding his child that was taken by the lord of the desert and who tries desperately to find his wife but he soon realizes that something wrong is happening, their was a great civil war among the Humtwuk as the Humtwiz and the Humtwar are waging war to the Humtwech because the 2 others vow a cult to the lord of the desert so that he spares them but the Humtwech believes that they should fight for survival.
NAME and his group soon joins the Humtwech for their similar goals and discover many things, NAME decides to settle the matter, trying to convince the Humtwuk to stop the war and killing the demon who caused all the problems in the Shahat Desert...
Hope you like it it took me like 10 minutes to think of that and i was too bored anyways haha