Why is NDSolve's StartingStepSize with ExplicitEuler not working? How do I set the step size?

You have to set MaxStepFraction, too, say, to 1.

Plot[
 Evaluate[
  NDSolveValue[{x'[t] == -x[t], x[0] == 1}, {x[t]}, {t, 0, 1}, 
   StartingStepSize -> 1, Method -> {"FixedStep", Method -> "ExplicitEuler"},
   MaxStepFraction -> 1]],
 {t, 0, 1},
 PlotRange -> All]

It's not a straight line because the value of the derivatives are stored & used in the InterpolatingFunction solution. However, we can see there are only two points.

sol /. t -> "Grid"
(*  {{{0.}, {1.}}}  *)

I would suggest (as an alternative) the following

pointsAndValues[x_InterpolatingFunction] :=
  Transpose[{First[x["Coordinates"]], x["ValuesOnGrid"]}];

ListPlot[
  pointsAndValues@
    First@NDSolveValue[{x'[t] == -x[t], x[0] == 1}, {x}, {t, 0, 3}, 
      StartingStepSize -> 1, 
      Method -> {"FixedStep", Method -> "ExplicitEuler"}, 
      MaxStepFraction -> 1], Joined -> True, PlotMarkers -> Automatic]

And to check the convergence use e.g.

ListPlot[pointsAndValues@
  First@NDSolveValue[{x'[t] == -x[t], x[0] == 1}, {x}, {t, 0, 2}, 
    StartingStepSize -> 1/#, 
    Method -> {"FixedStep", Method -> "ExplicitEuler"}, 
    MaxStepFraction -> 1] & /@ {1, 2, 4, 16}, Joined -> True, 
 PlotMarkers -> Automatic]