Spotify Shuffle (music playlist shuffle algorithm)
JavaScript (Node.js),  125  124 bytes
Saved 1 byte thanks to @KevinCruijssen

a=&gt;a.flatMap(a=&gt;a.sort(_=&gt;R()-.5).map(v=&gt;[(o++-.1+R()/5)/a.length,v],o=R()),R=Math.random).sort(([a],[b])=&gt;a-b).map(a=&gt;a[1])

Try it online!
Commented
a =&gt;                          // a[] = input
  a.flatMap(a =&gt;              // for each category a[] in a[]:
    a.sort(_ =&gt; R() - .5)     //   shuffle a[]
    .map(v =&gt;                 //   for each value v in a[]:
      [                       //     build a pair [position, value]:
        ( o++                 //       increment o
          - .1                //       subtract 1/10
          + R() / 5           //       add 2/10 * random value in [0,1)
        ) / a.length,         //       divide the result by the length of a[]
        v                     //       use v as the 2nd element
      ],                      //     end of pair
      o = R()                 //     start with o in [0,1)
    ),                        //   end of map()
    R = Math.random           //   R = alias for Math.random
  )                           // end of flatMap()
  .sort(([a], [b]) =&gt; a - b)  // sort by first element, in ascending order
  .map(a =&gt; a[1])             // keep only the 2nd element