When are you planning on camping and wheeling? Lots of public areas everywhere. Most of the areas in the east and NE this time of year are too cold for camping but would still make for great wheeling as day trips from a hotel.
Alamogordo has some good trails and warm enough, barely, to camp out. Ruidoso is a great place to stay and just up the mountain from Alamogordo. Skiing is available in Ruidoso, and if you are into that.
Summer time around Mills Canyon or Clayton Lake state park gets you off the beaten path and into some very pretty places. About the only place that doesn't have abundant public land would be the plains around Clovis.
Its a beautiful state, come on over and spend some money!!!