It's a paradox because Rose was the one who saved him.
If her father didn't die she'd have no reason to want to go back to that day, thus there would be nobody to save him, meaning he would die. That is the paradox, and that is why he had to die.
In the waters of Mars, there was a similar situation in which the death of Adelaide Brooke was temporarily prevented. Adelaide on the other hand didn't have to die. She could have lived on and whilst it would have changed future events it would not have been a Paradox, thus there would be no Reapers.
The case where River refused to shoot the doctor was technically a Paradox as the River that had already shot the doctor was present. Technically there is no reason that the Reapers shouldn't have been present, but there are explanations as to why they might not have been present. One explanation is that the Doctor and River's lives have more of an impact on time (both being time travellers and time lords, and the Doctor's large impact on the world). Another explanation is that time did unravel in father's day and that the reapers were actually from a different time zone or planet (though that would mean the Doctor's explanation was a lie for some reason or another).
Another case was the big bang, in which the Doctor effectively got himself out of the Pandorica with knowledge he acquired from effectively nowhere. This demonstrates a key example of a paradox where an effect is also its own cause (the doctor knew how to get himself out because he had seen Rory doing it after the Doctor's future self informed him how). That had a different effect because by that point time was collapsing anyway.
In short, a paradox will always cause damage to time, but results can vary based on the situation. In Fathers Day the paradox was small enough for time to attempt fix itself