How do you kill Fontaine with only 3 proximity mines? I tried on Easy and used the exact same setup, but the mines didn't even knock off half of his health.

For each phase you need to place 2 proxy mines, that takes him down to 1 HP and you shoot him with whatever. Since theres 3 phases you need 6 mines in total, not 3.

3 should still be able to get the kill off though. The only thing that could effect that is if you miss the upgrade station at the end of Neptune's Bounty. At the end of that level the upgrade station is used to upgrade launcher damage (only upgrade in the run). You'll know you're doing it right because Big Daddy's in Hephaestus won't take 5 shots (just 4) and Fontaine will take 3 proximity mines to kill (or 2 to get to 1hp like Smurfy said).

I got that upgrade, so I don't know what I'm doing wrong. Is it possible there's something wrong with the difficulty perhaps? Throughout the entire game I've had the feeling the difficulty was higher than Easy. I'm playing on the Steam version, version 1.1

That would be weird. Other checks are 1) The elevator skip. That jump is only possible in easy I believe (fall damage increases in higher difficulties). 2) telekenisis should be a one hit kill (although I believe that's the case in both easy and normal).

Did you notice big daddy's taking an extra shot as well? When you're in game and go into the options menu can you confirm that it says your difficulty is easy there?

Problem solved: Apparently the game didn't register me switching to Easy and it was on Medium the whole time. =P

That'll do it. It's a good idea to check that on whatever save file you use to start the run with (and then just never change that one). Good luck with the runs!