Steven,
There are a ton of amazing hikes in the Las Vegas area. I would suggest you keep on eye on the weather as it can already be 100+ degrees by the middle of May here in the desert.
Mt Charleston is a lot cooler then the Vegas valley since it's from 7,000-11,919 in elevation. The Charleston Peak loop hike is great but depends on snowfall of which we keep getting more snow because of El Nino.
Zion NP is a great place and you could easily spend a week there backpacking and hiking. Try St. George Shuttles which run like 9 times a day from the LV airport to St. George.
The north rim of the Grand Canyon is generally open by the middle of May but I don't think that there is any shuttle service that will take you there. There are lots of tour companies that will take you to the South Rim of the Grand Canyon.
Another area worth checking out is the Grand Staircase-Escalante National Monument in Southern Utah. But you would need a car to get there. GSENM is the largest National Monument in the lower 48 and you could spend months there checking out some amazing scenary.
You could be in the Southern Sierra's with a 4 hour drive across Death Valley Nat'l Park but once again you would need a car.
Red Rock is a great place for day hikes or climbing. You might be able to do an overnighter at Red Rock but have to be above 5,000 feet to camp out. Another great place for day hikes is Valley of Fire State park which is about an hour drive from Las Vegas. There are many tour companies that will take you there but no shuttle service that I know of.
Since I live in Las Vegas let me know if you need any specific questions answered. Have a great trip.
James