I'm based in London, so dropped it off with https://www.ismash.com/ in St Pancras. Was done in half an hour and cost £40. Can't vouch for the quality of the battery yet, but they are a pretty big chain now so I'm assuming it won't be awful.

However I've had batteries replaced (different phones) at the Apple Store before and it took about an hour.