I think your sandbox idea is a good one. You could even take up the patio part you were going to put grass in and instead of, grass put in sand. You could even make it a raised a little to keep the sand from spreading out. That would be very good on their feet... much better than the hard patio.