Actually, better yet, we should define "interesting behaviour"... there might be some miscommunication here.
I'm referring to any CA where a sort of "physics" develops, similar to the physics required for DB, where moving and stationary objects arise. I'm not suggesting finding a CA with fully self-replicating entities capable of evolution, I'm suggesting just finding a CA to provide a habitat for the bots. I was thinking the bots could be a sort of "black hole" of, say, 100 cells arranged in a circle. According to their DNA, they can change their shape to anything they want, and add or subtract cells from themselves. Any CA entity that is under it, such as a glider that hits it, disappears. Consuming cells of a certain state, say the "dying" cells of Brian's Brain, gives energy. I'm suggesting using dieing cells as energy since, in brian's brain, they indicate novel patterns emerging. And, of course, bots can shoot gliders and excrete still-lifes/oscillators.
EDIT:
Interesting side note: using CA physics eliminates many physics problems we were trying to solve before. For example, since spaceships (aka photons) are so common in brian's brain, plants can easily evolve as stationary bots waiting for spaceships, for example, coming from the top of the screen. Instantly, shadows and other phenomena similar to real-life occur spontaneously, without the need for ray-casting. This is the sort of spontaneously emerging physics I was referring to. Of course, there's gonna need to be some way to feed off of other bots, which I'm not sure of.
All in all, I think a CA-based implementation of DB is much more elegant than our current method of programming in the physics by hand. The goal of DB, after all, is for order and novelty to develop out of chaos. Not to mention that it'll be faster.
EDIT2:
EXAMPLE PLANT DNA
1: expand size into a straight line. //maximize surface area for absorbing spaceships falling from above
2: for each cell:
1: if hit by photon, then grow upward rand cells //grow upward, forming plant-like structures, avoiding shadows
3: cond energy>5000, delete 5 middle cells //reproduce
4: cond energy<500, delete cells until energy>500 or bot is less than 100 cells long. //eat body if energy too low
For animals, you can just fire spaceships at still-lifes, and consume the ensuing chaos.
EDIT3:
The best CA rule I've seen is known as starwars, based off of brian's brain but less chaotic, yet more interesting than GoL. Remember, GoL is just the most studied CA, not necessarily the best. Starwars forms interesting growing fractal structures, lots of spaceships, and highly ordered still-lifes with a constantly growing and changing exterior.
Brian's brain is also interesting, but it is really chaotic. Random configurations don't die out after a very long tie, so plants will have it too easy here.