Late May might be pushin' it with the snowpack in the Virgin River drainage this year, but you never know. Last year it ran huge and was unreal.
Your best bets: Zion National Park-Virgin River - below satans staircase to the visitors center (you've gotta' get a special permit from the visitors center now to get your car in there) beautiful boating though. And if the flows are right and you want some class IV satan's staircase is one of the best desert runs out there.
Virgin River Gorge - Class III, IV at big water. It's a long run but beautiful. Along I-15 just pass the arizona-utah border down to the nevada border (pick up some NV beer!)
Sevier River - beautiful mountain creek, class III, dam released flows.
My pops has a website that's got info on most of these and he knows all there is to know for the region. The website doesn't have a full guide, but some pics and flow guides. Post back if you've got questions.