What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?
Approximating volume of convex bodies

In Dyer et al.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38.1 (1991): 1-17.
a $O(n^{19})$ approximation algorithm was proposed.

The work of Lovász et al.: Simulated annealing in convex bodies and an $O^*(n^4)$ volume algorithm. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^*(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).



Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/