I'll only recommend Apple for a new battery. That said, there are tons of them on eBay if you care to DIY. Not an easy task.
No, you will not loose anything on the iPhone, however, prudence dictates that you do a backup before taking/sending it off.
Edit: This just in from Other World Computing (macsales.com) I highly recommend them also.
"The iPhone and iPods are another interesting example. Although Apple moved to internal batteries on the Unibody Macbook/MacBook Pros over the past year - these are pretty easy to swap none the less. At the same time, with each new iPod generation and the iPhones, it's gotten far more difficult to replace something so simple as the battery and is now really a professional service job. We offer the service for under $60 and Apple charges well over $80 for this battery replacement.... How many people do you think that go to Apple for a battery instead upgrade to new iPhone for the $99 or $199 instead?"