Deep cycle batteries are most often found in golf carts. They are usually a 6-volt, not 12 volt. They tend to have thicker plates and can withstand the constant charging/draining better than 12v batteries. You can buy 2 6-volts and wire them in a series (not parallel) to create a 12v system. This will not double your amp hour rating, but it will make them compatible with a 12v backup pump system. Generally, Trojan is one of the better known 6-volt brands. They require maintenance (water). If you want to go the maintenance free route, the best 12v deep cycle battery I know of is the Lifeline AGM made by Concorde. They are very pricey, but generally have thicker plates and are a higher quality battery vs. your cheaper marine options. Their 31T size has an amp hour rating of 105.
I don't mean to question you, but I would be extremely skeptical that you have a true 3/4 HP pump if it takes 45 sec to 1 minute to complete a pump cycle. Unless you have a double float pump switch and/or a pit the size of the Grand Canyon , then your pump rating is overrated IMHO. A Hydromatic VS33 1/3 HP can pump 40 GPM at a 10' head. A good 3/4 HP sewage pump would do around 150 GPM. Is your pump really doing 100+ gallons a cycle? A lifetime warranty won't do much for you if you flood again.