Progentius vs Cowardice
You are correct that Cowardice is of no benefit vs. Progenitus.  Declaring Progenitus to be the target of something is an illegal action so you back up to just before it was done, it doesn't "Happen but fizzle."

The easy way to keep track of protection is the acronym DEBT.

D - Damage, the thing you have protection from cannot damage you

E - Enchant and Equip, the thing you have protection from cannot enchant you or be equipped to you

B - Block, the thing you have protection from cannot block you

T - Target, the thing you have protection from cannot target you

So, for example, Day of Judgment can remove Progenitus because it does none of those things.  Fleshbag Marauder could also get rid of Progenitus if you have nothing else to sacrifice, etc.