The Rubik's Cube is a very natural (and to me, unexpected) example. An $n\times n\times n$ cube requires $\Theta(n^2/\log n)$ steps to solve. (Note that this is theta notation, so that's a tight upper and lower bound).
This is shown in this paper .
It may be worth mentioning that the complexity of solving specific instances of the Rubik's cube is
open, but conjectured to be NP-hard (discussed here for example) NP hard . The $\Theta(n^2/\log n)$ algorithm guarantees a solution, and it guarantees that all solutions are asymptotically optimal, but it may not solve specific instances optimally. Your definition of useful may or may not apply here, as Rubik's cubes are generally not solved with this algorithm (Kociemba's algorithm is generally used for small cubes as it gives fast, optimal solutions in practice).
 Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow. Algorithms for Solving Rubik's Cubes. Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), September 5–9, 2011, pages 689–700
 Erik D. Demaine, Sarah Eisenstat, and Mikhail Rudoy. Solving the Rubik's Cube Optimally is NP-complete. Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), February 28–March 3, 2018, pages 24:1-24:13.