Smathers Beach and Higgs Beach on the south side of the island are the biggies. Usual rules of only dig where a kid could build a sand castle. All the Keys beaches are pretty rocky so patience is required. Fort Zack Taylor State Park on the southwest corner of the island has some nice beaches, but I don't know what their MD regulations are. You could always stop at the front gate and ask.
