Before iOS 7 this was not possible or feasible since iTunes would restore an image of the OS that would be free from any locking. Now there is Activation Lock which neatly pre-empts any attempt to remove the Find My iPhone feature of iCloud. Effectively, with Find my iPhone, your device is effectively locked to your Apple ID.
For iOS 7 and later - enable Find My iPhone to prevent anyone else from erasing or using the device.
If my iOS 6 or less iPhone is stolen, can I remotely brick the thing, so resale value drops to zero?
The best you can do is to wipe the data from the device with an app like Find My iPhone from Apple or the open source Prey application. The device will no longer contain your applications or personal data, but it will still function normally and the thief could then initialize it for their own use.
For apps like Apple's Find My Phone, how feasible is it for a thief to remove the apps?
Without wiping the device? Hard to impossible. And that's the whole point of these applications: to keep your data safe and the cost of losing the hardware. You're essentially cleaning it for them and getting it ready for their use or resale. But you're ensuring that they can't gain access to your personal data, your PayPal account, your bank accounts and anything else you might have your phone connected to.
In the UK, cell phone carriers will blacklist phones that are reported stolen so they can't be used on the network again. The bigger UK carriers do it. Not sure how common a practice it is in North America, or if carriers here are willing to do it all.