It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ oracle queries, whereas the best classical oracle search algorithm requires $\sim N$ queries.
From this, it's often claimed that a quantum computing running Grover's algorithm could give useful speedups for many practical computational problems (since many such problems, e.g. numerical optimization, can be framed in this form).
But Grover's algorithm is a "black-box" algorithm that treats the oracle as the only method of getting any information at all about the solution to your problem. It completely ignores any possible correlations between the oracle's responses for different inputs, or any other "structure" behind the computation to be solved. Grover's algorithm therefore gives a square-root speedup over completely naive, brute-force search of every possible solution.
But it seems to me that (loosely speaking), most "interesting" or "practical" computational problems have enough structure that complete brute-force guessing is rarely the best classical approach. As a simple example, for numerically optimizing some complicated but differentiable function, gradient descent (plus some means of escaping from local minima) is typically vastly more efficient than random sampling.
Now an exponential (classical) speedup over brute-force guessing is too much to hope for in general: if $\mathrm{P} \neq \mathrm{NP}$ (which is presumably the case), then there exist problems in NP that do not admit exponential (classical) improvements over brute-force guessing that work even in the worst case. But even NP-complete problems often admit heuristic algorithms that allow for efficient solutions "in practice", e.g. they work for most problem instances. Even when this is not the case, my intuition is that most "practical" problems admit classical algorithms that provide an algebraic speedup over brute-force guessing that is better than square-root, at least for many problem instances. So my intuition is that for most "practical" problems, there's usually a heuristic classical algorithm that's more efficient than using Grover's algorithm for a square-root speedup over brute-force search.1
Is my intuition correct? Are they many practical problems for which the best known classical algorithms deliver less than a square-root speedup over brute force guessing "in practice"? (I guess the somewhat sharper version of "in practice" means "in the average case", but I'm also interested in less formal interpretations of "in practice" as well.) More bluntly, would a quantum computing running Grover's algorithm actually be that useful for many practical computational problems?
(Strictly speaking, this is just a question about classical algorithms, but I think this is the right place to ask it, because people here are more likely to have thought about quantum speedups for these kind of problems.)
1 The only type of problem for which I wouldn't expect any classical algorithm to provide a significant improvement over brute-force search is one where the mathematical structure has been deliberately chosen to be as complicated and obfuscated as possible. For example, inverting cryptographic hash functions or cracking a symmetric-key encryption algorithm like AES. This means that, ironically, the only type of math problem for which I can intuitively see Grover's algorithm delivering a clear quantum speedup is breaking symmetric-key encryption and hashes. (This is ironic because the main application for the other most famous quantum algorithm, Shor's algorithm, is of course also for breaking cryptography, although public-key rather than symmetric-key.)
