How many miles overall are you looking for?
What elevation are you coming in from?
What difficulty are you looking for (i.e. summits are high altitude and steep but gorgeous)
What's your level of acceptable other people?
I've been hiking here for 2 years around the front range (denver area to rocky mountain national park) and here's my observations for that early in the season:
Plan on the mosquitoes being out in droves, even in the areas still full of snow on the trail. For many areas, plan on slogging through tons of melting snow drifts even if the weather is in the 80's at the trail head.
Bring snow baskets on your poles. Consider snow shoes if you'll be summiting from the north side. No amount of waterproof shoes and knee high gaiters will prevent your feet from being soaked if you are on a trail with snow melt.
Some spots are practically glaicers with combinations of re-freezing snow melt and slippery slops into raging rivers - Katoohla Microspikes wouldn't be a bad investment in spots as crampons offer a lot more safty.
They don't start giving out wilderness permits until June 1 for a reason - trails over 8,000 feet that aren't in southern exposure are often in horrible condition until mid June at least. the trails look like snow drifts every 6 feet with a river running under foot. You start up a drift and end up punching through and slogging through until your hip deep. It drains energy and slows you down to a crawl.
Lost Creek Wilderness has a lower average elevation and may offer suitable options. Indian Peaks is excellent, but not that time of year (slosh fest). Probably the same from many trails in Rocky Mountain National Park. I unfortunately haven't been to Flat Tops Wilderness or the Weminuche Wilderness during that time of year to tell you, but the rangers around here are helpful and often quite knowledgable, so call the ranger district and ask for advice.
Find yourself trails that are on the southern exposure for your best bet. Many of them are already clear (it's been sunny and in the 50-60's), even over 10,000 ft, but as soon as your in the shade it can be 4-6 feet deep.
All that said, I'll be out there hiking too, so at least you won't be suffering alone. My hiking season started 2 weeks ago, I just learn to adjust my trails to shorter spans that are melted off or ask the rangers for the most compacted snow trails so I only need to pack microspikes and can forgo the snow shoes.