Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading to a better bound on an existing algorithm
I thought matrix multiplication was an example of this, but I have talked myself out of it (perhaps incorrectly!) after trying to understand Coppersmith–Winograd and its friends better.
The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that quickly.
Based on brief scans of the papers, it appears that the algorithm was invented by Hopcroft and Ullman3, who gave an (incorrect) $O(n)$ time bound. Fischer4 then found the mistake in the proof and gave an $O(n \log\log n)$ time bound. Next, Hopcroft and Ullman5 gave an $O(n \log ^*n)$ time bound, after which Tarjan1 found the (optimal) $O(n \alpha(n))$ time bound.
1 R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" (1975).
2 B.S. Galler and M.J. Fischer, "An improved equivalence algorithm" (1964).
3 J.E. Hopcroft and J.D. Ullman, "A linear list merging algorithm" (1971).
4 M.J. Fischer, "Efficiency of equivalence algorithms" (1972).
5 J.E. Hopcroft and J.D. Ullman, "Set-merging algorithms" (1973).
The algorithm of Paturi, Pudlák, Saks and Zane (PPSZ) for $k\text{-} \mathrm{SAT}$ had been known to have a running time of $O(1.364^n)$ for $3\text{-}\mathrm{SAT}$, with a better bound of $O(1.308^n)$ for formulas guaranteed to have a unique satisfying assignment. Later Hertli gave an improved analysis showing that this improved run-time bound also holds for the general case, thus showing PPSZ to be the best algorithm for $3\text{-}\mathrm{SAT}$ known at the time.
There is now also a further improved analysis of the algorithm, yielding the bound $O(1.307^n)$ for $3\text{-}\mathrm{SAT}$, due to Scheder.
The Logjam Attack mentions that analysis of the general number field sieve (as applied to computing discrete logarithms over $\mathbb{F}_p$) descent step was tightend, see top left of the 3rd page. As this is the only step that can't be pre-computed (if $\mathbb{F}_p$ is fixed), its efficiency was instrumental to their attack.
The initial analysis appears to be in Gordon 92, where descent was costed similarly to precomputation, at $L_p(1/3, 3^{2/3})$. The tighter analysis seems to be from Barbulescu's thesis, where descent is costed at $L_p(1/3, 1.232)$, where: $$L_p(v, c) = \exp((c+o(1))(\log p)^v (\log \log p)^{1-v})$$ It's worth mentioning that this is technically an expected cost, and not an upper bound. This still seems in the spirit of the question to me, but I'll remove it if it's not what you're looking for.
Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm for the minimum $k$-cut problem has, in fact, asymptotic time complexity $O(n^{k+o(1)})$, improving on the original analysis which gave $O(n^{2k-2})$ (and on previous work by the same authors, which obtained a different algorithm running in time $O(n^{1.98k+O(1)})$).
This is likely to be (near)optimal, based on a conditional lower bound of $\Omega(n^k)$.
Note: A talk by Jason Li (and the corresponding slides) can be found on the TCS+ website.
[1] The Karger—Stein Algorithm is Optimal for $k$-cut, Anupam Gupta, Euiwoong Lee, Jason Li. arXiv:1911.09165, 2019.
The work function algorithm for $k$-server was shown to be $(2k-1)$-competitive by Koutsoupias and Papadimitriou - the algorithm was known previously and analyzed only in special cases. It is conjectured to be $k$-competitive.
The $3$-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers [1] [2]) The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the choices are specifically-chosen in a certain way, it allows for a more refined analysis, that is where the improvement comes in. And I think his Appendices in 1 give a more refined analysis (counting subproblems/substructures) leading to better recurrences and so better runtimes. I think there are a number of such examples in the parameterized complexity literature, where adding another variable to the analysis can lead to improved runtimes, but I have been out of that game for several years now and I can't think of specific ones at the moment. There are a number of papers in FPT and PTAS areas that come up when looking for "improved analysis" in the paper titles.
If specifying choices counts as the same algorithm (like union-find's depth-rank heuristic), then the Edmonds-Karp algorithm is an 'improved analysis' of Ford-Fulkerson, and I'd imagine there are plenty of other problems that have algorithms that have seen runtime improvements from new choice rules.
Then there are a whole bunch of amortized analysis of existing algorithms (I think union-find fits under this description, here is another one https://link.springer.com/article/10.1007/s00453-004-1145-7 )
