>Treemaps struggle with data that is either (wide and shallow) or (thin and deep).

That hasn't been my experience. If treemaps have a limitation is that they can't deal well with very large numbers of highly homogeneous items (e.g. all nearly the same size). The worst case is if you have to show over a million items of the same size in a 1000x1000 bitmap.