Hey, I'll be heading out there around the same time, hitting GC, Antelope Canyon, Monument Valley and some other places.
Never been to GC before, but have been to Antelope, MV and that area before. I would recommend a tele in general. I found myself using one in Monument Valley a few times actually, because of the restrictions of staying on the roads and how far the mesas sometimes are from where you're shooting from. I'd also find myself pulling over on the road at times and shooting at something in the distance.
I used Carol Bigthumb's group for Upper Antelope, couldn't have been happier:
http://www.navajoantelopecanyon.com/index.html
If you didn't know, there's Upper and Lower Antelope. Upper is more crowded and is easy to walk through, Lower has some tight areas and ladders/stairs, and because of that is generally less crowded.
I liked Carol's group because my guide was terrific (friendly, joking, offering photographic advice), and he and the other guides I saw from their company made a big effort to get other tourists out of our shots, unlike guides from other groups, many of which seemed bored to just want to get through. I got lucky and my group merged with another group led by Carol's son inside the canyon, so my guide actually took myself and one other 'serious' photographer aside at times and just showed the two of use specific locations and angles to shoot from that the bigger group skipped.
Also, at the time (last November) Carol said if I went to Lower (you just drive up, don't hire a company) and keep my receipt, then took it to Carol's (lot is near Upper Antelope parking lot) and show them the receipt same day, they'd give me a discount on the Upper Antelope tour. I think it was $20. I didn't get to test that , since I went to Upper and Lower on separate days due to circumstances.
Side note: At Lower Antelope, definitely go for the Photography tour. Navajo site says there's a restriction of two hours, so they gave me a badge with a time written on it that was 2 hours away (actually since I was going in at 30 minutes past, the guy gave me 2 1/2 hours). But if you go past that, they just charge you an extra $20 or something per hour, and your on your own without a guide. You'll just get other guides walking past and glancing at your badge. No one commented on mine when I went past the time limit. But, that was the off season, things may be different in May when it's more crowded.
I used my 10-22mm almost exclusively in both canyons (cropped body). I did switch to my 24-105L once, but that was risky with the fine dust floating around in there. This time I'm taking two bodies, so I won't have to switch lenses. Of course, bring a tripod if you can, cable release etc. Bring something for the dust you may get on your lenses, and bring everything with you (water, spare memory cards, batteries etc), you won't be able to go back to your car. Well, in Lower you probably can, but that's valuable time you'll pay for.
I could ramble on more with advice/recommendations, but I'm getting OT (unless you specifically want more, haha).