I think that lack of parallelism has almost nothing to do with graphs vs lists. It would be pretty easy to either store the entire dependency graph's fetching-critical metadata in each image or to make it possible to fetch the metadata separately from the core data. Both of those would allow you to parallelize downloading of image data in the graph-based system.
Having more granular layers can help a bit but in practice it hits its limits very quickly because higher layers will necessarily get swept up and have to be rebuilt when layers below them that they don't actually depend on get rebuilt. This rules out having a core image and a set of modules that each downstream image may or may not need (to be mixed in or not per-image). Thus, when you use the layer-based system in practice you usually end up with very little layer sharing between images, outside of the core Linux distro layers.
Having more granular layers can help a bit but in practice it hits its limits very quickly because higher layers will necessarily get swept up and have to be rebuilt when layers below them that they don't actually depend on get rebuilt. This rules out having a core image and a set of modules that each downstream image may or may not need (to be mixed in or not per-image). Thus, when you use the layer-based system in practice you usually end up with very little layer sharing between images, outside of the core Linux distro layers.