"The only time I've used my phone for navigation while walking was to check what time it was so I could work out which direction was north."
I don't buy expensive phones but every one I've had for the last 6 years or so has had a perfectly adequate compass.
Edit - as for the complaint about Google Maps not showing orientation while walking, is this because it doesn't actually know what direction your phone is pointing in relative to your viewpoint? If you hold it vertically, the compass doesn't work. And a cursory look around shows many people seem unable to look at the screen unless they hold it in front of their faces.