Figuring out who goes next is not remotely as difficult as you have made it out to be. Where I used to live, I would go through two four-way stops twice each day during peak traffic. There are generally two scenarios when you approach the intersection. In light traffic, you get to the intersection and nobody else is waiting to cross, or it is obvious who got there first. In moderate traffic, you will queue up behind one or possibly two cars. Once you get to the front of the queue, you wait for the cars on your left and right that are already at the front of the queue, and then you go. This is simple because each direction of traffic alternates, and it is reasonably fast because the queues are very short.

The real worst case scenario is that during light traffic four cars approach simultaneously, but not only is this extremely rare, but it is not really even a problem when it happens.

In my personal experience I have had far, far more problems in US cities on two-way stops when I am bicycling and a driver incorrectly yields when they have right of way.

I suspect that most Americans feel the same way about roundabouts that, say, Germans feel about 4-way stops. But please remember that roundabouts require more land and much more capital investment. The tradeoffs in the US are different.