Spore already has to rate as one of my favourite games, even though I have never actually played it. Unlike other, more linear games, Spore allows you to create a creature and slowly slowly add features to it, and evolve it over time.
Spore, being interactive (as it would have to be; it's a video game) lets you play God, which is probably one of the many factors that will determine its success. Now let's take a step in the other direction. I have found some videos of what some call "the Blind Watchmaker", and as you may have guessed, it's not exactly interactive, but no less interesting.
These programs are basically evolution simulators. They make simple 3D creatures over several generations mutate slightly to grow new limbs, and also mutate in the way that these limbs are affected. Natural selection means that useless limbs don't crop up (or atleast stay on the body). Basically, here we have a Darwinian evolution simulator. Now regardless of your beliefs, I can guarantee that this will be fascinating.
Here is one of my favourite videos:
http://youtube.com/watch?v=gFWDxqcZqvY
This one bares some similarity to certain Earth-like creatures:
http://youtube.com/watch?v=j2lSPg2kY-c&feature=related
This one is one of the most efficient:
http://youtube.com/watch?v=l-qOBi2tAnI&feature=related
And the amazing thing about this is that as complex as they look, they really aren't too difficult to understand. Basically, put it like this: There are two part to it, the body and the control system. The body system also has two parts: the node system that contains the information for the body, and the body itself, which is just a 3D representation of the node system. The node system, also, contains two parts: the nodes themselfs and connections. To summarise, a node with a connection to itself would look like an infinite amount of cubes attached in a line (though limits are put to make sure you dont get infinite limbs). A node with two connections to itself would look like a fractal tree, each with two branches. Two nodes connected would basically look like two joined cubes. Each node and connection has parameters too, for example, the size of limbs, and the types of joints.
The control system is probably simpler. A limb gets stimulated by touching something. This stimulation is sent to the "brain" (presumably in a simple binary form), and the brain sends back an effector signal. The signal comes in the form of either a force or a torque for a limb. This means things like when a creature touches the ground it will start to walk. Even more interesting, creatures have been made that start to walk when there is a ball on it's back.
Here is the detailed paper exlaining it all:
http://www.karlsims.com/papers/siggraph94.pdf
As interesting as this is, it seems pretty useless. Or is it? You may be good at designing creatures, and you may be good at animating them. What if you're bad at both? Well if you need a quick solution, these would be extremely useful. Making them look better wouldn't take too much effort either. A node for example could have data about what type of shape it is, like cone, or a mesh. It could also hold data about textures. All of the parameters about the creature's structure and the brain could be saved to a file, ready for loading when you want to play your game.
Finally, here's another video for you. I simply love how efficiently these little guys walk:
http://youtube.com/watch?v=uS57VNvq0o4
I smell a new project for some, heheh.
Don't you just hate that Zotoaster guy?