Why not shard the bakers?

https://blog.nomadic-labs.com/florence-our-next-protocol-upgrade-proposal.html

Depth First Execution Order: Previously, intercontract calls were executed in a so-called “breadth first” ordering. This was believed to be the correct choice when the Tezos protocol was initially designed, but it has turned out to significantly complicate the lives of smart contract developers. If Florence is adopted, the calling convention will change to a “depth first” execution order. This will make it far easier to reason about intercontract calls.

As the Florence protocol replaces BFS with DFS I believe these agora posts are relevant to your sharding question