If you've never seen this kind of thing before, the canonical PC example is The Powder Toy, which is so amazing I wish there a 3D Minecraft-like version. But it's really CPU-heavy even in 2d.
Observe boiling water.
But when I put oil (in a separate compartment) beneath the bowl of water, and light it on fire, the oil burns off, but doesn't boil any water.
What should happen? All I see is the surface 'sparkle' effect that is the same as still water.
There are a couple of other 3D falling sand games (http://csiuo.com/Sand3d/, https://github.com/TheTomster/sandish, https://powdertoy.co.uk/Discussions/Thread/View.html%3FThrea...) but none of them are very good due to the factors you mentioned. UX is also a pretty big problem, as traditional mouse or touch controls don't work well in 3D, which is why I wanted to go the VR route, but something like a very dynamic Minecraft as you mentioned could work as well.
Most falling sand game implementations are sequential, so parallelizing the simulation using a margolus neighborhood (https://en.wikipedia.org/wiki/Block_cellular_automaton) or double buffer could greatly improve performance. Most falling sand games tend to not be pure cellular automata, and some are implemented as particle systems with particle in cell grid collision instead of CA, but particle and fluid sims are easy to parallelize. I haven't seen a falling sand game (2D or 3D) that runs entirely on the GPU, and my goal was to do that, eventually ending up with some complex Claybook (https://www.claybookgame.com/) style engine.
still great though.