Do you need to have a randomly shaped polygon of a specific size? If so, that would require some programming.
What if you create a fishnet of rectangular polygons (using the create fishnet tool in Toolbox, and a new attribute (type double) for the fishnet, populate the new attribute with random values, figure out your sample size, then select that many polygons from the fishnet?