There are several shops in Leipzig renting out shops. The challenging thing there is that the websites for these shops are all in German. However, I am quite sure that calling them in English will be no problem. From the list, I can pick out some that I would recommend:
Bikeandsport: Because they are at the main train station in Leipzig and therefore very easy to find.
Kuehnis: They have a very pricing statement on the website, deliver the bike to you even.
Little John: They have several stations nationwide, 3 of them in Leipzig.
Maybe also Grupetto: They have several stations across the city that rent out bikes, but most of them are in hotels. If you stay at one of these hotels, you will have access to these bikes.