> > The most difficult question (as usual) is color selection
> > for sub-exps faces.  I think the most intuitive would be a rainbow.
> 
> Well, let's first install one of those patches and then see what
> improvements are needed.  So what matters is not really the color
> selection, but the cleanliness of the code so we can easily change the
> color selection.

The color selection is somewhat important, IMO.  Wrt this, have a look at the
coloring I use for this kind of thing in Icicles search.

Example:
http://www.emacswiki.org/emacs/Icicles_-_Search_Commands%2c_Overview#SearchHighl
ightingContextLevels (also attached)

I use 8 search-context levels, that is, 8 regexp group levels, with a different
face for each.  Past 8 levels the face sequence repeats.

One of the attached screenshots shows the 8 faces.  For a dark background mode,
there are corresponding dark colors.  In practice these colors work pretty well.
Note that there are two subsequences, the second one (levels 5-8) being a less
saturated (paler) version of the first one (levels 1-4).

The face (color) definitions are here:
http://www.emacswiki.org/emacs/icicles-face.el

Not sure what you had in mind by "cleanliness of the code so we can easily
change the color selection".  In my case, I use separate faces, so users can
easily customize them.

I picked the default colors by tweaking (using palette.el).  I picked the
dark-background colors by starting with the complements of the light-background
colors (and then modifying a bit, IIRC).  I probably got some user feedback on
the dark-background colors (I use a light background, myself), but I don't
remember.

HTH.