Agree that Zion and especially Bryce will be cold/miserable in March, most likely.
Your more recent suggestion would be pretty good, Joshua is still relatively high and will be cold at night, if you're camping.
The coast will be much more temperate, but probably a bit far from Vegas.
What about Death Valley? Some good exploration through there, even on the road - though really good on a GS of some description. Weather is absolutely perfect in Death Valley in March.