Why do many Arabic letters look exactly like other letters except for dots, yet have no similarity in sound?
The first thing to understand is that the Arabic alphabet derives from the form of the Aramaic alphabet used by the Nabataeans, itself derived from the Phoenician alphabet, and ultimately Egyptian Hieroglyphs.
Comparing the Aramaic alphabet (I'm specifically using the Hebrew form of it here, because Nabataean unicode isn't, and Hebrew is generally better known and supported than Syriac) in the traditional abjadi order with the Arabic alphabet we see the following Arabic letters missing:
The first six correspond to phonemes lost in Aramaic:
In these cases, there is (or was) some similarity in sound, although it may not be clear comparing the modern Arabic sounds of these letters. In particular, whilst most of these differ only in a single feature even today, ḍād ض ṣād ص are generally reconstructed as something like *tɬʼ *tsʼ in the earliest stages of Semitic (when the merger occurred in Phoenician), whilst ẓāʾ ظ ṭāʾ ط are generally reconstructed as something like *tθʼ *tʼ at that same stage, meaning they also differed only by a single feature ([+lateral] in the case of ḍād ض ṣād ص, and [+spirant] in the case of *tθʼ *tʼ)
Originally, Arabic writers mostly didn't distinguish between these letters (all letters were written without dots of any kind). This sort of underspecification is not very unusual cross-linguistically (look at English not distinguishing θ & ð in spelling, with both being <th>).
Later, people wanted to be able to ensure that they were reciting the Qurʾān with the correct pronunciation, and not accidentally reading dāl where they should be reading ḏāl etc. Because of this the system of dots developed* to disambiguate between the multiple phonemes represented by each letter. In each case, the Aramaic pronunciation does not receive a dot, and the pronunciation particular to Arabic does (in this respect, we can compare to Modern Hebrew use of geresh).
Prior to the system of dots, Arabic had also used šīn ש for both the sounds now written sīn س and šīn ش (this is likely due to the complicated correspondence between sibilants between Arabic and Aramaic, but that's a topic for another question), and Aramaic semkaṯ ס was not used. With the system of dots, sīn س (which represents the same sound) was given its position in the abjadi order. In this instance however, note that sīn س is the letter without the dot, despite the fact that Aramaic šīn ש (from which both letters derive) had the sound of šīn ش.
The other big category of dot distinctions arose because the Arabic alphabet descends from an especially calligraphic form of the Nabataean script, and this resulted in a bunch of other letters being written the same (or very similarly), despite being pronounced in multiple ways even in Aramaic.
Here the correspondences have no phonetic basis, and occurred purely due to visual similarity in earlier stages.
When dots were introduced to disambiguate the letters for Arabic phonemes not present in Aramaic, they were also introduced to disambiguate these letters.
Lastly, there is hamzah ء. This one is complicated, and appears to have developed as a result of dialect mixing within Arabic between Old Hejazi (the dialect represented in the Consonantal Text of the Qur'an), which had lost the sound originally represented by ʾalif ا in many or most positions, and started to use the letter to mark long vowels, including those without an etymological ʾalif ا, and other varieties that had preserved them. Thus it became necessary to indicate which instances of ʾalif ا should actually be pronounced, and this was indicated with a small copy of the letter ʿayn ع (which later developed into the modern hamzah ء).
Marijn van Putten is an expert on the development of the Arabic alphabet, especially in relation to the Quranic text, and has written a much more in-depth explanation here (in particular discussing different stages and scripts within Arabic).
* This is the common narrative, but as van Putten notes, doesn't match the historical evidence perfectly. It seems that the system of dots actually predates the standardisation of the Quranic text. It may still have provided motivation behind the system becoming near universal.
N.b. the diagram in the question is in Hijāʾī order, and uses a non-standard Romanisation of Arabic. I have generally used more typical "scholarly" Romanisations of Arabic, but always included the letter in the original script as well to avoid confusion. As is fairly common, I have in many instances used the name of the modern Arabic letter to stand for the Arabic phoneme and its antecedents. I hope it is sufficiently clear when I have done so.