I live on the border of se1 and se16 and find Thrifty car hire convenient. They have a very wide range of vehicles. Their pricing is set on Monday morning and increases as more cars are rented. You therefore often pay half the price on Monday morning as you would on a Friday afternoon. I hope that makes sense..
It's just the other side of the railway bridge, where Andersons Travel, the coach place, is. Nice cars, sometimes cheap-ish, but the service leaves a little to be desired - or at least it does based on my experience there a few weeks back.