There are known solutions to the Navier-Stokes equations. A simple example would be laminar shear-driven flow between two moving plates. Just as in the case of Einstein's equations, the known solutions regard simple situations with particular boundary conditions; a general solution that covers all possible cases is not known in either case. One should not expect such a thing ever to be found, since these systems can exhibit chaos; the difficulty of finding a general solution is the same as for the n-body problem in Newtonian gravity.
However, the millennium problem for the Navier-Stokes equations is something different. It doesn't ask for a single solution, it asks whether a solution always exists, for any initial and boundary conditions. Then, if solutions do always exist, it asks whether they will always have certain technical properties. But it doesn't ask us to find the solution, because we know that in general this will not be possible.
I'm no expert, but I believe the reason this is harder for the Navier-Stokes equations than for Einstein's equations is that the Navier-Stokes equations for an incompressible fluid are inherently non-local; the incompressibility constraint means that something happening in one part of the fluid can instantly affect every other part of the system. (This is, of course, an approximation to the physical reality.) In contrast, general relativity is inherently local.