I really don't see the benefit of randomly generating Shapes. There isn't much to be revealed with a rectangle that say covers one small part of the pacific ocean and another rectangle which covers another small part. The number of possible Shapes is just too massive to ever reveal anything.
What I feel would be better is if we defined Shapes that test particularly troublesome areas. Datelines, equators, poles. We can also include massive Shapes and tiny Shapes, circles, points, and whatever else we end up supporting.
Having this standardized Shape suite would be a big benefit to testing all the Strategys. I don't think it would be particularly difficult to create and once created, it wouldn't require much maintenance at all.