I know that 5 years ago there were shuttles between St. George and Vegas, and within the park there are shuttles. The problem would be getting from St. G to the park. I'm sure there is something. I'd call Zion Adventure Company, and do it now while they're slow. Good people and local knowledge. Depending on the thaw, the Narrows might or might not have too much water to hike that time of year.
Red Rock is a huge place. You'd be able to find solitude out behind the main canyon area, but it'd require some x-c navigation and (that time of year) hauling a bunch of water.
It'd be pretty darn hot in the Grand Canyon that time of year, too. I presume all shuttles go to the south rim area. A good 3-4 day loop for an experienced hiker who isn't as experienced canyon hiker would be to go down the South Kaibab, across the Tonto, and up the Grandview trail. Doable in May, but I'd be hauling a bunch of water in places, and doing dawn starts with a nice 4 hour siesta in the shade from 11-3 or so.
Sure you can't rent a car? Driving to and hiking on the North Rim of the Grand Canyon might be the best option of all.