Google won the search engine market because it was objectively better and thus spread through word of mouth. The first time I saw Google run actual ads was when they pushed Chrome hard.

Facebook also spread mostly through word of mouth and only started doing ads when its public image deteriorated.

(Side-note: I'm in Germany, so this is about German ad campaigns. Also I have had adblockers for a long time, so when I say "they run ads", I mostly mean TV, print and billboards.)