Kth best problem that is NP-hard for K polynomial
Here is an example of something fairly contrived, but which might be a good starting place for reductions to other problems:

Input:  a boolean formula $\phi$ and a satisfying assignment $x$.
Goal:  find a satisfying assignment $y$ to $\phi$ which has as few variables set to true as possible, but at least as many variables set to true as in $x$

This (well, its decision variant) is obviously in $\mathsf{P}$ ($x$ is itself a solution), but finding the next-best assignment (forcing $y \ne x$) is $\mathsf{NP}$-hard: you can force all satisfying assignments to an arbitrary formula to have a superfluous 1, and then plant the all-zeros assignment. You can also fairly easily plant as many (polynomially many, possibly more if you're clever) assignments as you want.