Quantity of Art.

This is our first, and particularly thorny problem. Procedural techniques are the mooted solution. They can be used effectively as this demo shows. However, the tool used to create this is the product of several years on/off work.

Here are some examples of procedural techniques at work: firstly for textures.

The Unreal engine uses procedural textures to animate fire and other things in real time. Perlin noise is the old standby for generating textures for wood, marble, and fire, but has become something of an artistic cliche.

The most interesting technique I have seen on my travels around the web recently is that of using Steerable Pyramids which seems to be able to synthesize a promising range of textures.

Secondly: landscapes.

landscapes are another natural subject for procedural generation as they are closely related to textures - indeed, a terrain can easily be seen as a huge bumpmap. I am only point to a couple of open source tools here: Terraform and Demeter as terrain generation techniques are already well known and plastered all over the web.

Thirdly: interiors.

Interiors are a subset of cityscapes, a city being a set of interiors. The classic "interior" however, is the dungeon crawl dungeon.

There's a nice a-life technique for carving out 'interesting' dungeons and a 3d counterpart.
I suspect the former technique could be extended to 3d by having the ai creatures carve out voxels on a 3d grid instead of rectangles on a 2d grid, or perhaps a different approach via extruding a floor plan, similar to this Doom level generator would be more fruitful?

Fourthly: cityscapes.

Not much seems to be extant in this area. This strikes me as strange, as buildings are regular structures and should be inherently easier to model procedurally than the 'organic' forms of terrain, clouds, and fire which are often modeled procedurally.

The virtual terrain project has a set of notes on the subject which indicate the magnitude of the problem.

It must be said that they are setting their sights pretty high by trying to model the architecture of all possible schools in all areas of the world over all history. A more limited means range may be achievable via a set of suitable shape grammars. Just to prove I'm not talking out of my hat here, I can point to a paper written by some researchers who have actually implemented this to generate a viable cityscape.

Fifthly: and most importantly...Characters

For generating and manipulating character models there are plenty of tools available commercially that could conceivably save a procedural representation of a generated character: Character Studio, Poser and Creature Creator to name a few.
Blender also has the open source "make human" script. However, these don't deal with the thorny issue of animating the results. Inverse Kinematics is a nice technique for procedural animation, but constraining it to realistic - looking solutions is a non-trivial problem. I suspect the solution lies in the domain of
evolutionary computing or genetic algorithms, but until a good, cheap procedural model of bipedal and quadripedal locomotion comes along (and it's a hot research topic) I don't know.