I have the "Erase All Data after 10 failed passcode attempts" feature turned on on my iPhone 4S. I also have the "Find my Phone" app installed. If my iPhone was stolen, and the thief triggered the "Erase All Data" feature after failing to unlock the phone, would it erase the "Find my phone" app meaning I couldn't locate it through iCloud?
The 'Find My iPhone' app on the iPhone itself does nothing to affect the ability to locate/remote message/remote wipe the iPhone itself. The 'Find My iPhone' app is a client to simplify the functions of doing so for other devices.
In order to actually use those features on the iPhone itself MUST be configured via
Location Services > (down at the bottom)
Find My iPhone. Only by enabling that will you actually be able to locate your phone via another iOS device, or at icloud.com;
Yes. Enabling this option is both risky and safe. On one hand, you risk losing your phone/data forever, but on the other hand that individual will not be able to access your data or use your phone. It's your call, but I'd recommend leaving it off so you at least have a chance at getting it back. You can always wipe out your phone remotely with Find my iPhone without having that option enabled.
Yes. Unfortunately, Find my iPhone isn't a fail-safe system. It's also disabled if someone else erases all your data, through iTunes for example. Additionally, if a SIM card other than your own is put into the phone, the handset can only locate itself via wi-fi, and not through the third party networks SIM.