As the supply is ELV and it is going shipboard, I would avoid stepping up to LV which might not be expected and might require additional safety precautions.
You could use a transformer to step down the AC by any convenient ratio, 2:1 would be fine, which when rectified and smoothed would give about 18V DC. If you were making a lot of these you could have a tiny autotransformer wound with a tap at say 75% and get 28V DC. I am assuming from the wide range of acceptable DC voltages that the supply does not need to be regulated.
The easiest and neatest off-the-shelf method that avoids going to LV and the one I'd probably use would be to rectify, smooth, convert voltage with a DC-DC converter such as:
Tracopower's THD 10-4815WIN
Buy Isolated DC-DC Converters 10 W Isolated DC-DC Converter / Vout 24 V dc, 416 mA 1.2 % 1 % TRACOPOWER THD 10-4815WIN online from RS for next day delivery.
Suggest bridge rectifier first...output to LM7815 reg, this will give stable 15v dc out.
The snag there is that the maximum input voltage of 78xx regs is 35V so nothing gained. You would have to use a higher rated part, however using any linear regulator, (Vsupply-Vout)*Iout will be dissipated as heat, so the highest output voltage will give the coolest running, especially if the input power of the load device is constant wrt changing supply voltage. The OP didn't say what it is but 9-36V is a standard 4:1 DC-DC converter input range so it might well be constant power. In that case:
For a 15V reg, Ploss=(38-15)*5/15=7.7W making the efficiency 39% and requiring a sizeable heatsink.
For a 30V reg, Ploss=(38-30)*5/30=1.3W making the efficiency 79% and hardly any heatsink needed.
But I'd use the DC-DC.