My theory on why this might matter even for people who knew how to use the operators is this: With OR as default, you would first try your query without operators, get page upon page of irrelevant results, and then start to narrow your query down. With AND as the default, you would type in the query, and if you only got a few irrelevant results, or often no results at all, you would try alternative terms instead.
It seems that progressing from no result to desired results by choosing alternative terms just makes more sense than having to wade through irrelevant stuff, and the default encourages one methodology over the other.
Today, it's very hard to make Google return no results at all. Not just because the amount of content grew to an unimaginable scale in the meantime, but also because Google has become way, way fuzzier in the way it interprets search terms, likely to better suit a larger and different audience. A lot of times today, I have to switch to "verbatim" mode first, at least for technical stuff.
1. entering 'invisible marmalade teapot' and getting no results
2. changing to 'invisible marmalade teapot with tartan cosy', again nothing
3. so 'invisible marmalade teapot with tartan cosy in outer space', ditto
You: do you have that new crime novel in stock?
Bookseller: er, i don't know which one you mean?
Y: the new crime novel by john grisham, pelican something or other?
B: oh, right, yes, here it is!
default OR in a search engine would mean my first example eventually starting to return results about transparent space coffee pots with tartan cosies, ignoring the first few terms but the rest match, which is often helpful, particularly if you're doing an exploratory search for something where you aren't sure of the exact details.
I don't find your examples compelling.
If you want to do an additional search that does not depend on your first terms, you simply bring up a new search window.
In your 'real world' example, the equivalent search queries would go something like
search: new crime novel
result: way way too much stuff
search: new crime novel john grisham pelican
result: exactly the right book because every one of those terms applies
9130 webpages agree with you.
To switch on Verbatim, I click "Verbatim" on the left side of the google page, it appears just under the alternative, "All results". I think for other systems it can be well hidden in menus. I use it almost every time I google anything. Otherwise you get a load of irrelevant crap.
The reason being you can just search twice if you want either word, but in the vast majority of cases you want both words when you enter them in the searchbox. Most companies kind of split the difference and put the AND results first then fill in with OR results, but that mostly just leads to "if your answer isn't on the first page, it's not going to be on the second or the hundredth".
IMO this was one of the biggest contributors to the perceived quality advantage of Google vs AV.
Relevant xkcd about the “second page of Google results” effect:
It always took 2 to 5 searches using Altavista to get the results you were looking for. This was a huge improvement on Excite and Lycos which might produce infinite results with absolutely nothing relevant. There was a lot of noise like source code archives. With Google search the first page usually had a useful result.
Probably the biggest thing that destroyed Alta Vista was the horrible flashing banner Ads at the top of the screen.
My recollection is that Alta Vista supported boolean operators, but defaulted to OR while Google defaulted to AND. So searching Alta Vista for something like "$CommonWord $UncommonWord" would return results with high-ranking pages for $CommonWord that drown out all the low-scoring pages for $UncommonWord, whereas Google would return results that match the intersection (which would actually be relevant to the user's query). I'm convinced this default might have made a bigger impact on Google's success than any PageRank magic.