We are only interested in day hikes.
Yes you can definitely hike Zion/Bryce in May. In fact it is a good time of the year for hiking in that area. A sedan will do just fine for most trailheads.
Zion has only one unpaved road you're likely to want to drive on: a one-mile stretch of the Lava Point road. That road is marked on the map as "impassible when wet", which I suspect means an SUV won't do any better than a sedan in bad weather; it's not marked as high-clearance, so a sedan will do just fine in good weather.
There are no unpaved roads in Bryce; the roads are either open to everything or closed to all traffic depending on the conditions.