I think it would be...I've done the downhill from a campsite in CNM to Fruita on my mountain bike. I think it would be a PITA to ride along the frontage road to the west entrance of CNM on a mountain bike, but it is definitely doable. You should take a weekend to explore Fruita for mountain biking and jeeping. I know it's a little far for you, but it is a beautiful area, and not as crowded as Moab.