It is often said that Simon’s algorithm provided the first example of an exponential speedup over the best known classical algorithm. However, the Deutsch-Jozsa algorithm was published before Simon’s and looks to me that it also provides an exponential speedup since it solves the problem by making a single query while in the worst case Deutsch-Jozsa needs 2^n-1 + 1 queries on a classical computer. What is the proper analysis for Deutsch-Jozsa and what kind of speedup it achieves?
The confusion likely stems from deciding what counts as a "classical algorithm".
The Deutsch-Jozsa algorithm (DJ) provides exponential speedup over a deterministic classical computer on determining whether a function $f$ is constant or balanced, with the promise that exactly one of these is true. However soon as you allow your classical computer to perform random sampling of $f$, and tolerate small failure probability, the quantum advantage disappears. Since random sampling is a realistic feature of classical computers, one could argue DJ does not show a true advantage over classically accessible models of computation.
Simon's algorithm, on the other hand, demonstrates exponential speedup even over probabilistic computers. More formally, Simon's provides an oracle separation between BQP (class of problems efficiently solvable by quantum computers) and BPP (class of problems efficiently solvable by classical computers).
To summarize, if "classical algorithm" is defined to include reasonable access to random sampling, then Simons is indeed the first algorithm to prove exponential quantum speedup.