I'm also with "return them". Having ruined my feet (seriously-5 foot surgeries with a possible 6th in my future) in the name of fashion, I beg all of you younger gals to be very cautious about what you wear as it will come back to haunt you as a senior. Keep the crazy stilettos for occasion dressing only. Those sandals on the other hand, are supposed to be comfortable and to suffer for a chunky walking summer sandal is nuts in my opinion. But, if you're determined to keep them go buy one of the shoe stretch sprays (I've had success with Meltonian) and spray the heck out of the underside as much as you can and then go get a broom or mop (laughing yet?) and carefully position the top of it under the tight points and whack it a bunch of times with some force on a cement surface so you don't damage floors. Keep changing the position of where the top of the broom is positioned on the strap to get as much stretch as you need, where you need it.
This will work on leather lined shoes-it will not work on anything with a synthetic lining as only the leather will give and stay stretched. Synthetic will bounce back to original shape.
This is the technique traditionally used for lifting a toe box on a closed pump but it should help on a wide strap sandal too. It's an old "shoe dog" retail trick.
There is also another option I can think of but it will be pricey and I personally think it's nuts to put a ton more into Frye's but if you have a good cobbler who can really measure with them on, that strap possibly can be released a tiny bit and re-inserted or just professionally stretched out by him.
I'm assuming that the shoe fits you correctly and that the strap is just a bit too tight on you. Good luck and post back and let us know what worked.