Okay, in my unhappiness with some aspects of Spore, I've started to think about some possible ways to create a game featuring the same basic progression of scales, but with a more evolvy feel rather than focusing on the arbitrary aesthetics.
One of the issues with this kind of game is that each scale has such distinct machinery. A space ship isn't terribly similar to an amoeba, especially not aesthetically. But - but! It's possible to represent them using the same underlying algorithms.
Lets say you start off as a simple cell, just chugging through freefloating molecules. In the course of evolving, you don't simply evolve flagella or cilia (or spines and eyeballs): you also evolve internal "organelles". See Wikipedia.
All those internal structures aren't just for kicks. They radically enhance the capabilities of the cell in ways that aren't about moving or eating things. But, if anything, they're more important.
Thing is, trying to build a system that can evolve those organisms in an "organic" way, step by step... that's pretty difficult, and it wouldn't be much fun to play.
However, if you look at the organelles, you see something interesting: most of them are equivalent to organs (hence their names) in term of overall functionality. And most devices' internal components ALSO serve the same basic functionality.
If we give up on trying for realism, we can throw out the idea that we need to simulate these with any kind of care, and instead we can simply express them by fiat. "Oh, the endoplasmic reticulum is basically the circulatory system of the cell," we can handwave, "and a nation has roads, and a starship has plumbing/ductwork."
It's not accurate, but it's serviceable.
Then we can offer up a specific set of evolutionary options to the player - a kind of mutation system that is weighted by gameplay - and let him choose. He doesn't have to try to foster some kind of subcellular machinery: we can handwave a very primitive "circulatory system" into existence, and he can choose it - and continue to improve it by choosing in favor of mutations with better circulatory systems in further generations.
This same handwaving can be applied to the internal evolution of just about everything, if we don't mind a certain loss of realism. We can even talk about subsequent generations of cars: cars don't reproduce, but the same basic laws govern their evolution in a society. So we could allow the player to selectively "breed" cars for preferred options. We could even apply this to nations, cities, perhaps even ecosystems...
More external modifications, such as growing eyes or wheels, are a bit more dependent on scope and type of interaction. A cell won't grow wheels, and a car won't grow flagella - but they do serve the same basic purpose. In different mediums, different specific implementations are prevalent.
For example, there are little boats that do use flagella. We call them oars, though. Some even use a single oar out the back. You can easily argue that this is the same basic idea: different scale, same basic medium. More advanced boats evolve sails (flicking fins) or turbines (jellyfish and octopus use a roughly analogous method). We can talk about airside boat evolution and waterside boat evolution: maybe oars are flicking fins and sails are more like a primitive bird wing. Any way you run it, the basic ideas are the same: in any given medium, the same external evolutions will happen.
There are a lot of issues to consider. Transitions are important: when does a cell turn into a multicellular organism? We have rules on how multicellular organisms can develop organs (made of cells), and how cellular organisms can develop organs (made of molecules), but between the two is a bit iffy.
Similarly, not all evolution uses the same components. A tribe might become radically more advanced if it makes a tribal "organ" by domesticating animals. Those animals are not tribe members any more than the structures of the cell are DNA. But there has to be some kind of reason or source to the development: we can't just say "oh, look, something so arbitrarily handwavy that it's incomprehensible!"
(Plus, we want to support "zooming in", if you want to see how a tribesman lives.)
Anyway, the advantage to this kind of abstraction is computation. If we develop organelles as algorithmic components rather than some kind of complex chemical stew, we can abstract the operation of the whole cell to a very simple algorithm. Then, if we're treating organs in a multicellular organism as algorithmic components rather than huge assemblies of cells, we can simulate the whole organism as a simple algorithm...
Downside being, of course, that it's more or less impossible to actually make.