Its hard to explain, or even to grasp, how fundamental basic arithmetic is to almost everything in math.
I disagree. Not hard to explain at all. Point the person at a page of geometry problems and say, "Imagine struggling with 90 + 90 at the same time as you struggle with the concepts here." Point the person at a page of polynomials to factor and say, "Imagine trying to do these if you hadn't memorized basic multiplication facts." And so on.
I still believe that the long division algorithm taught isn't so useful.
At the risk of not knowing precisely which algorithm you're talking about, I can't imagine one that doesn't work by taking a large/hard division problem and breaking it down into small/easy division problems. And that's useful because it's a great example of what math does for your thinking.
To be specific, I think the important principle math teaches is that, when faced with a big, hard problem, break it down into smaller, easier problems. I would rather describe math as a "learn how to break down problems" discipline rather than use the vague and pretentious "learn how to think" description. All areas of education help your thinking.
If you ask me 9 * 7 I still do 10 * 7 = 70 - 7 = 63 in my head; but, I seem to handle spectral graph theory just fine.
I hate to admit it, but I am now a believer that strong arithmetic skills are important, and drills get you there. I don't like to call it memorization, since I'm not sure it necessarily is simply memorization. But you do need the answers at a moments thought. It should be as natural as saying a word.
And its not to say that you don't teach concepts concurrently... but that the arithmetic is fundamental.
That said, I still believe that the long division algorithm taught isn't so useful. :-)