Just my 2c...
Having an internationally accredited certificate in machinery safety, all that I can tell you for certain is that all of the opinions above are more or less just that - opinions. The actual legislation is extremely (and deliberately) vague, and interpretations of it vary wildly.
I do a lot of work at one particular company that must have every machine's safety system validated by an external party before it can be handed over to the operators. In large part, the company they get to do the validation is chosen based on what kind of safety arrangement is in place, and what we know of the companies and their particular interpretations of the "rules".
An example: validation company A will not validate anything as Cat 3 or 4 if there is an e/stop and a guard switch in series. Period. Even though I know full well that many of the company A employees disagree with that assessment - and so do I, in many cases - that's the company line, and they have to toe it. Validation company B, on the other hand, will see an e/stop and a guard switch in series and ask a lot more questions about how many operators use the machine at once, where they are stationed, how often and for what purpose the guard is opened, and so on. After assessing all of these factors, they decide whether or not they will validate it as Cat 3. Quite often they will. So, if they get in a machine that has an e/stop and a guard switch in series, they'll call company B to do the validation. Maybe it'll pass without any further modifications, maybe it won't - but it definitely won't if they call in company A.
All of the responses above are potentially valid observations, but they are absolutely not universal. And even if they can be justified and backed up, ultimately it doesn't matter if the person who's validating/assessing/reviewing your design has a different take on it.
As for my own opinion on the difference between Cat 3 and Cat 4? The only actual explicit difference I can find in the international machinery safety standard (ISO13849-1) is this:
Cat 3: Wherever reasonably practical, single faults will be detected at or before the next demand on the safety system (6.2.6)
Cat 4: A single fault will be detected at or before the next demand on the safety system (6.2.7)
"Wherever reasonably practical". Hardly a black and white, easily definable rule, is it!