This thread had attracted some strong opinions. I now have a prototype working which has practically zero impact on runtime. I have added a Fremen UU, "Fremen Soldier", which is a duplicate of the normal soldier. Except, it can move into any desert terrain, and when it does so, it gets a unit art swap to Worm Rider Soldier. A Worm Rider Soldier has a movement of 3 and can travel on any terrain. When a Worm Rider Soldier steps on land terrain, it gets a unit art swap back to Fremen Soldier.
Effectively, the soldier is now a unit which can travel on desert at movement 3, plus the graphics are cooler. Right now, the unit art for Worm Rider Soldier just points to the basic sandworm, so you will see a wormsign sand dome. Someday we may have a "Ridden Worm" graphic where the worm travels above ground.
This requires two units to be added for each unit which will "convert". I will add the Fremen Settler, Worker and Scout, for four unique units. This should make the Fremen strong early game and raider units. I can add it for later Fremen units, as long as the list is not too huge. Probably these are the only UU that Fremen will need.
(The runtime issue I reported in the 1.3.6 release note was not due to graphics. I keep forgetting, and painfully relearning, that you should never kill or add units in the middle of the AI movement loop.)
Now that the performance issue is avoided, does anybody have any real objection to this? I like it a lot better than training Worm Riders in cities, especially now that I have changed the worm to disallow movement onto land in 1.3.7.