All methods based on Groebner bases are exponential in complexity. Polyhedral homotopy might be better in theory and is often better in practice, in terms of speed at least. Though there is an initialization step that is not cheap.
I do not know of any solver in Mathematica which would be faster than NSolve and not require an initial guess. Maybe try FindMinimum or NMinimize on the sum of squares is about all that comes to mind.
