Of course it should. The Linux cli is as good a gateway to understanding of the world around you as the Commodore 64 and the Apple II clis were for me as a kid.
If you start a child off with Windows or Mac, look forward to them maybe not ever understanding what a directory is, or that a computer has two types of memory. Consciously choosing and paying a premium to learn computing from Windows or Mac OS sounds to me only mildly better than trying to learn computing with a Playstation. They're simply not meant to be user serviceable.
I don't know what to say about not teaching children computing. There's a better case for teaching computing than any other science, if you judge usefulness by daily opportunity to use your skills to understand and improve your situation. The only reason I'd be against it is because I love being overpaid to do simple work due to the ignorance of the general population of the machines that completely run their lives.
My goal for a childhood education in computing would be to produce an adult that understands the capacity and flexibility of computing, and can be trusted to manage or hire computer workers, an adult who won't over or underestimate what can be done with computers, and an adult that has a deep relationship with the devices which, from now on, are going to be in physical contact with them at all times.
Yes, it's more important than learning how to fix your car. I've never had a car. How many people can say that about a computer? How many people can say that about a computer without ignoring embedded devices?