Fuse Question and Surge Protectors
I would suggest a single 15A circuit breaker in series initially instead of a fuse. Fuses at 16A could cook and can be problematic. Also, using the relay at stated rating could have heat problems. For a properly designed device, protection should be designed for the power tap as well as the load.

As for a surge protector, MOV's are the most common to use and most common to fail. You would probably want your VPR around 600V to prevent any unwanted early failures.

Both the circuit breaker and surge protection should be as close to the power inlet as possible, in front of everything else.