Deep cycle batteries typically have thicker electrode plates, higher density active "battery" material and a more rigid construction. Deep cycle is a battery industry term to help market batteries. In essence, it is supposed to mean you can cycle the battery, while extracting more Ah (capacity) many times, with longer life.
BUT, there are so many variables that can contribute to this being an industry term. Without going into technical details. I personally would compare self-discharge rates (how long can the battery sit, without charging, at a given temperature as to have enough "juice" to run "some" distance back to a charging station. You can also look at how quickly that battery pack can charge (if that is an option or feasible).
I'm much more familiar with NiMH batteries though.