Terrorism is actually not as widespread as you think in the RP, but the risk does exist like anywhere. And to answer your question, yes the Mindanao region would be the main area in question.
While I haven't been down there, I have traveled and dived in the RP and can say that the Philippines is one of the easier countries in SE Asia to get about in due to English being taught widely in school and actually used on a semi-regular basis.
And yeah, I have met single western women out there. Common sense and vigilence prevail.
http://wikitravel.org/en/Apo_Island
Oh check out ita software for cheapest fares. They dont really change much depending on where you are, unless you are in a west coast gateway city (LAX,SFO) Fares from LAX usually run around $800ish, you can find specials from time to time from $500 on up. Flying from a non west coast gateway, you are probably looking at the $900 and up region.
Lowest fares I find are usually CI, with a connection in TPE.