Why did the F of "sneeze" and "snore" change to an S in English history?

It was still pronounced as 's', but 's' used to be written down as 'f'.

Similar to when you see 'ye olde' - a 'y' was pronounced as what we now write as 'th'.

So it was a written change rather than a sound change.

Word Histories contains:

The verb fnese having gone out of use early in the 15th century, its place was mainly supplied by neeze, meaning to sneeze, first recorded around 1325. The adoption of sneeze was probably assisted by its phonetic appropriateness, that is to say, it may have been felt as a strengthened form of neeze. ... Neese/neeze is still found in Scotland, Northern Ireland, and Northern England. [adapted]

This seems to imply a movement involving first an eliding of the awkward f, and a later addition of the s in line with say snore. Apparently, AHD 3rd edition espouses this etymology.

.......

But Word Histories also contains:

The verb sneeze is an alteration of fnese due to misreading or misprinting it as ſnese (= snese) after the initial consonant cluster fn- had become unfamiliar.

For instance, in William Caxton’s 1483 edition of The festyuall, by the Augustinian canon regular John Mirk (floruit late 14th-early 15th centuries), the spelling is fnese, whereas it is snese in the 1508 edition by Wynkyn de Worde (here, the verb means to snort)....

This implies a single-step switch in pronunciation. A mumpsimus ... but an explanation AHD3 considers a folk etymology.

Edwin Ashworth's answer is basically right, but I'm going to shed some light on its linguistics.

Every language has a unique set of rules that govern the permissible sequences of sounds (which sounds are allowed to make a consonant cluster i.e. licit and illicit sequences of sounds). A sequence that is possible in one language may not be allowed in another, for instance, the cluster [pn-] is allowed in Greek, but not in English therefore the ‹p› in the word pneumonia is silent in English, but pronounced in Greek. These specific rules are called phonotactics.

In simple words, phonotactics studies what sounds go together, and where can they be found. I have explained English Phonotactics in an answer to your previous question.

Over time, a language may undergo phonotactic variation and change. For example, the letter K in the word know wasn't silent until Modern English (it was pronounced in Middle English and Old English). The letter K went silent probably because it was awkward for Modern English speakers to pronounce a nasal (/m n ŋ/) right after a plosive (/p t k b d g/) in the same syllable. The plosive is therefore silent in words like pneumonia, know, gnome etc.

The tautosyllabic cluster (within the same syllable) /fn-/ is ill-formed in Modern English. The same thing might have happened to it. It might have become 'awkward to pronounce' and English speakers either dropped the /f/ or changed it to /s/.

According to The Cambridge Handbook of English Historical Linguistics by Merja Kytö, Päivi Pahta:

Historical changes in phonotactics are documented for English. For instance, the sequence /fn-/ was found in Old English in words like fnēosan ‘sneeze; gasp’, fnær(ett)an ‘snore’ (Lutz 1991: 234) but was later lost either by a shift of /f-/ to /s-/ or due to replacement by another word, e.g. fnēosan ‘gasp’→Old Norse gasp or Anglo-Norman pant(Lutz 1991: 236).

Though it doesn't explain why the /f/ became /s/.

Also from Duisburg-Essen's website:

The set of permissible combinations has varied over the history of English, either by elements being lost, cf. /x/ and /ɣ/ above, or by the simplification or alteration of cluster types. In Old English /h/ and /w/ could occur before /r/ and /l/ as in hlaf /hl-/ ‘loaf’ or writan /wr-/ ‘write’; /h/ could also occur before /n/ as in hnutu /hn-/ ‘nut’ Such clusters were simplified during Middle English and only the second element of each cluster prevailed. Initial clusters like /fn-/ in fneosan ‘sneeze’ were changed to /sn-/. The combinations /gn-/ and /kn-/, as in gnagan ‘gnaw’ and cnēo ‘knee’ respectively, seem to have survived well into the Middle English period.

According to Phonotactics of consonant clusters in the history of English by Katarzyna Dziubalska-Kołaczyk, /fn-/ lost the /f/ and was replaced by /s/ in some words e.g. fnēosan > sneeze.

She further says:

Apart from being replaced by /sn-/, /fn-/ also changed into /g-/, e.g. fnasten > gasp.
[...] /fn-/ → /n-/ (→/sn-/)

And,

"Fricative + nasal" belongs to the medial cluster space, so the change from /fn-/ to /sn-/ does not essentially improve the cluster, although /s/ is stronger than /f/ and as such improves the perceptual distance between C1 and C2. The change to a single consonant is a change to CV.

Another interesting explanation of /f/ to /s/ shift can be found in For the Love of Language: An Introduction to Linguistics by Kate Burridge, Tonya N. Stebbins (p136). They propose the idea of phonaesthemes. They claim that the change from /fn-/ to /sn-/ is because there weren't many fn- words left in English* and there were so many words with the phonaestheme sn-. The phonaestheme sn- is often found in words dealing with the nose: snore, snorkel, sniff, sniffle, snuffle, snuff, snivel, snout, snoot, snub, snot, snob, snotty, sneer, sneeze, snoop. The fact that so many sn- words had something to do with 'nose' eliminated fn- and made sneeze a natural fit.

        * ^{Both *fnast and *fnese are also labelled 'obsolete' in the OED [Consonant Change in English Worldwide]}

---

Now there's a concept of Minimal Sonority Distance for onset clusters. I have explained sonority in this answer.

Minimal Sonority Distance:
Sounds of a language are divided into several degrees on a scale according to their sonority. In English, four degrees have been proposed for glides and other consonants.

Sonority scale of English consonants and glides:

• Glides [j w] -> 4
• Liquids [l ɹ] -> 3
• Nasals [m n] -> 2
• Obstruents [f t k] -> 1

There is a requirement on the Minimal Sonority Distance (MSD) between the two sounds in an onset cluster. In English the MSD is assumed to be 2 i.e. the sonority of the second sound must be at least two degrees higher than that of the first.

For instance, the sonority of [n] is 2 and that of [f] is 1 -> 2 - 1 = 1 while the required MSD is 2, so the cluster [fn-] is ill-formed and no Modern English word starts with [fn-].

Now for the cluster [fl-] (as in fly): the sonority of [l] is 3 and that of [f] is 1 -> 3 - 1 = 2, it conforms to MSD, therefore the cluster [fl-] is well-formed.

[sn-] is an exception to MSD. Here's a whole paper on the unusual behaviour of /s/.

         ^{[Simplified from Two Theories of Onset Clusters by San Duanmu]}

There are many other exceptions, however. (See Two Theories of Onset Clusters by San Duanmu for exceptions and their solutions).

The OED gives

sneeze (v.)

Etymology: apparently an alteration of fnese v., due to misreading or misprinting it as ‘ſnese’, [edit: ſ = the "long" letter 's'] after the initial combination fn- had become unfamiliar.

Fnese had apparently gone out of use early in the 15th cent., its place being mainly supplied by nese neeze v. The adoption of sneeze was probably assisted by its phonetic appropriateness; it may have been felt as a strengthened form of neeze.

In the following places where sn- is printed in modern editions the correct reading is fn-: Trevisa Higden (Rolls) V. 389; [etc.]

1495 Trevisa's Bartholomeus De Proprietatibus Rerum (de Worde) xvii. xxxviii. 625 Yf it [sc. cummin] is..blowen in to the nosethrilles,..it makith a man snese [Bodl. MS. fnese].

Interestingly, the OED does not give the same etymology for "snore", which, according to it, seems to always have been "snore".

The Old English Translator gives

fnora (n.) weak 1. a sneeze 2. sneezing