Let's say I have Progenitus on my side of the field, and my friend plays Worldfire. Would Progenitus still be on the field after Worldfire resolves or is he also exiled since he has "Protection from everything?"
Your Progenitus would still be exiled.
According to the Gatherer rulings:
2/1/2009: “Protection from everything” means the following: Progenitus can't be blocked, Progenitus can't be enchanted or equipped, Progenitus can't be the target of spells or abilities, and all damage that would be dealt to Progenitus is prevented.
2/1/2009: Progenitus can still be affected by effects that don't target it or deal damage to it (such as Day of Judgment).
Since Worldfire doesn't target anything, Progenitus will be exiled along with everything else.