FPGA Initialization / Reset

"..., all outputs are initialized low. " -- I think you mean to say all registers are initialized low, by default.

"all outputs" can be inferred to mean all output pins of the device, which is not correct.

Registers (and thus state machine initial state) can be set to either 1 or 0 on powerup (ie, the default value after configuration).

They can then also be set to 1 or 0 on occurrence of a reset signal (which may be different than the powerup state.

Ie, a simple verilog example that configures two registers foo and bar to be low (same as the default) and high on configuration.

reg foo = 0;
reg bar = 1;

always @(posedge clk or posedge rst) begin
  if (rst) begin
    foo <= 1;
    bar <= 0;
  end else begin
    foo <= bar;
    bar <= ~foo;
  end
end

"..., but this will be after everything starts low." ... I don't believe this is correct if you use the reg statement with an initial value.

and re: state machine init value, you could do something like:

...
localparam INIT =3'b101;
...
reg [2:0] STATE = INIT;
...