Is there a known polynomial time complexity problem with bad constants?

As you know, big O notation hides all constants. For instance, both runtimes $T_1=n$ and $T_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$).
Is there an iconic problem whose best known solution has a terrible (large) constant in the runtime expression?

A simple one: Given n chess positions, find an optimal move for each position.

The game of chess is finite, so finding an optimal move for any position is O(1), and for n positions it is O(n). With a huge constant.

StackExchange Computer Science Q#162843, answer score: 13