Just make it big, very big. Well, it’s not just that…- yet we’ll probably agree that megafauna fruits are, in some sense, overbuilt.
If we take the two major types of fruits that extant megafauna consume (e.g., elephants, rhino, etc.), we find two distinct typoplogies. Both are extremely large-sized fruits forms. The first one is like a drupaceous mega-cherry, a large fruit with a single, or very few (i.e., up to three or four) large individual seeds; the second type is kind of a mega-tomato, a large fruit with many, really many (up to hundreds), tiny seeds. Fruits of the first type are usually 4-10 cm diameter; those of the second type are usually > 10 cm in diameter.

Why do these fruit types differ when compared to other ‘normal’ fuits? It is not simply that they are much larger. Their key characteristic is that, for a given number of seeds per fruit, they pack up seed sizes up to three orders of magnitude larger than ‘normal’ fruits. Thus, megafaunal fruits allowed plants to circumvent the trade-off between seed size and dispersal by relying on frugivores able to disperse enormous seed loads over long-distances.

In addition to these two types of megafaunal (fleshy) fruits, the extinct Pleistocene megafauna most likely also dispersed grass seeds and seeds attached to their fur (epizoochoric).
Barlow, C. (2001) Anachronistic fruits and the ghosts who haunt them. Arnoldia, 61, 14–21.
Bretting, P.K. 1986. Changes in fruit shape in Proboscidea parviflora ssp. parviflora (Martyniaceae) with domestication. Economic Botany, 40, 170-176.
Feer, F. (1995) Morphology of fruits dispersed by African forest elephants.
African Journal of Ecology, 33, 279–284.
Guimarães Jr., P.R., Galetti, M. & Jordano, P. (2008) Seed dispersal anachronisms: rethinking the fruits extinct megafauna ate. PLoS ONE, 3, e1745.
Janzen, D. & Martin, P.S. (1982) Neotropical anachronisms: the fruits the gomphotheres ate. Science, 215, 19–27.
Janzen, D. (1984) Dispersal of small seeds by big herbivores: foliage is the fruit. American Naturalist, 123, 338–353.