I've always thought deep underwater would make sense, provided the containment was very good. You would never have to worry about a meltdown really since there's an unlimited heat sink readily available and the reactor could be constructed to passively cool itself through convection in a total failure / walk away scenario.

Problem is that if you break containment water will carry all that nasty radioactive material everywhere. I'd look at ceramic fuel packaging such as pebble beds or sealed fuel rods that are highly water insoluble, then waste vitrification or encasement in highly water insoluble glass or ceramic materials.