I always carry M&C, but for on-trail travel in most AZ terrain I find an altimeter much more useful than a compass. If you check a few times an hour and track your progress, you can usually pinpoint location with a single, easy observation. It weighs less than a GPS and the battery is good for years. Unless you spend a lot of time cross-fixing landmarks, an altimeter usually gives earlier indication than a compass of being lost. Of course, once you are sufficiently "lost" (insert your own definition here), you darn well better have a compass and know how to use it.
When applicable, the altimeter navigation approach also requires minimal cognitive abilities, which can help if you're fatigued, hypothermic, dehydrated, in panic, or not that bright to begin with.
I can't compare with GPS since I've never used one, but I suppose it would be just as convenient. I'd like to try one sometime. However, I would never trust anything electronic as my sole means of navigation (and yes, I usually carry a small, cheap backup compass).