Methods for NSolve

To answer part b):

Here are some settings meth for Method -> meth for NSolve:

"EndomorphismMatrix"
"CompanionMatrix"
"Legacy"
"Aberth"
"JenkinsTraub"
"Homotopy"

I found them by searching on the site, and you can find various discussions of them by search for each one. This question, closely related to this one, also seems relevant:

What algorithms does NSolve use?

In addition, options can be passed via the Method option, in the from Method -> {subopt -> value,...}. These may be found this way:

Internal`NSolveOptions[]
(* V10 result:
  {"ComplexEquationMethod" -> Automatic, "MonomialOrder" -> Automatic, 
   "ReorderVariables" -> True, "SelectCriterion" -> (True &), 
   "Tolerance" -> 0, "UseSlicingHyperplanes" -> True}
*)

The basic algorithm might be the same yet the underlying data types are certainly different. Generally, plain old arithmetic with exact rationals is much slower than machine arithmetic with floating point approximations, particularly if the underlying integers grow larger than the largest machine integer on your system, which is 9223372036854775807 on my Mac. Here's an example where the only difference is the starting point, 1 vs 1.0:

Nest[1 + 1/# &, 1, 1000000]; // Timing
Nest[1 + 1/# &, 1.0, 1000000]; // Timing
(* Out:
  {4.714536, Null}

  {0.031917, Null}
*)