Best of the Southwest US (mid to late March)?

Big Bend east of Moab is a worth a stop for bouldering. Roadside and some cool problems, though the best ones start at v4. The Needles in Canyonlands is great for a first desert backpack, but permits might be hard to come by. Thankfully you can check online availability right now: https://canypermits.nps.gov/index.cfm. You might get lucky. Indian Creek outside the Needles has great climbing, but almost nothing you can toprope. There's been a fair bit of bouldering development in the area, and you might be able to tag along and TR with some folks if you bribe them with beer. There's some great roof crack bouldering along the Roadside Ruin trail in the park.

Escalante has a few good options for your next backpack. No permits needed. Either Coyote Gulch or a loop down Silver Falls Creek and up Choprock would be my suggestion.

If those backpacks went well and you feel like you could do more I'd gun for the Tapeats-Deer Creek loop in the Grand Canyon. You need a permit, and this is quite a bit harder, but well worth it.

There's bouldering a TRing in a few spots in Zion, and a ton of great bouldering in Moe's Valley and other places down around St. George. If Needles doesn't work out, or even if it does, it's worth going up to Joe's Valley to boulder for a while. Phenomenal rock and more climbing than your skin can stand, with great problems of all difficulties.

You might visit Chaco Canyon for some world class ruins and some nice day hikes out to them. But pay attention to the weather. Like a lot of dirt roads in the four corners area, impassable in a normal car when they get wet from rain.

Get a copy of Michael Kelsey's book: Non-Technical Canyon Hiking Guide to the Colorado Plateau.

billy

I can't comment on Utah, Arizona, and NM. Others know much more.
As for the Colorado Springs area, depending on what kind of weather the Front Range gets leading up to your trip, there is some decent areas, some of which are totally free of snow.
I do some camping and backpacking in Cheyenne Canyon here in COS year round. I'd be happy to recommend some good trails. Especially if this warm weather sticks around for you…
Near Canon City, which is close to COS, there is a VERY popular area for climbers, which has opportunities for car camping, and backpacking. The area is off of Shelf Rd, in canon city. Camped snow free, just last month off the rd.

Edited for clarity

Another area in Utah worth considering is the San Rafael Swell. No permits needed and possible to do some extended non-technical canyon backpacking. Steve Allen's guide is a classic, if flawed. There is also Kelsey's guide, supposed to be a good read but he does have a reputation for understating the difficulties of his routes. The area itself is great and off the beaten path, well worth checking out.