Decision problems in $\mathsf{P}$ without fast algorithms
Perhaps the following problems fit into your examples: 


(The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms 
for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
AKS-primality test in $O((\log n)^{12})$ time. 
Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.