Is it just a matter of coincidence or did the two language influence each other in some way?
It is partly accidental and partly due to common PIE heritage. Let's look at a few similarities:
1) Lenition of intervocalic voiced occlusives - /b/, /d/, /g/ in Spanish and Greek have a fricative realisation between vowels and occlusive realisaiton at the beginning of the word and after a nasal.
This is a very frequent evolution of voiced occlusives. In fact, it happened in all western Romance languages to a degree (little in Italian, a lot in Spanish, massively in French - to a degree where even the resulting fricative got elided). Similar thing happened in Greek and many other languages. The reason behind this is thought to be that voiced occlusives produces only little pressure on the occlusion (because of glottis vibrating) and thus there is little need for the articulators to be pressed together tightly (as opposed to unvoiced), so the occlusive can easily become a fricative.
2) Apical /s/
In both languages there is just a single articulatory position for a sibilant, so it has a fairly wide space of articulation as there is not contrast in this space (e.g. compared to English or French distinguishing prealveolar /s/ and post-alveolar /š/), so the (Castillian) Spanish and Greek sounds are perceptually something in between.
In Greek, this is thought to be a direct inheritance from Proto-Indo-European, where the situation was probably similar. In Spanish, you could theoretically say the same but the situation is far more complicated. It is very likely, apical /s/ was present also in Latin as a direct heritage from PIE (and there it evolved often into /r/ in intervocalic position). Proto-romance and Old Spanish develop, however, a set of other sibilants, coming mostly from palatalised velar occlusives /k,g/. So they had, at one stage probably the following system of sibilants - dental, apicoalveolar and postalveolar (voiced and unvoiced). The ternary contrast is difficult to maintain, so it evolved. In most Romance languages, these merged to prealveolar [s,z] and postalveolar [š,ž]. In Spanish, the ternary contrast did not disapear but was reinforced - dental sibilants moved to interdental fricatives (like English TH in "death"), postalveolar sibilants moved to retroflex and later to velar fricatives, while the apical /s/ remained. Then the voicedness contrast was lost. You can see the reflexes of this in early Spanish loandwords in other languages, e.g. "don Quijote/Quixote" is pronounced [kišot] in French, and the name "Borja" (then pronounced [borža]) was rendered as "Borgia" in Italian.
3) Similar phonotactics - Ancient Greek words could end only with a vowel, or /s,r,n/ (not sure about current Greek though), Spanish words today typically end only with /s,r,l,n,d/.
It is very common in languages that word end consonants, particularly occlusives get dropped because very often they do not have any audible release and are only distinguished by formant transient on the preceding vowel, which may be a too weak cue.
4) Vowel system
Both languages have the set of five vowels /a,e,i,o,u/ but this is probably the most common vowel set in the languages of the world.
So in summary: The PIE phonology evolved through different pathways into the various descendant languages and by accident, the Spanish and Greek followed some of the same pathways or pathways giving a similar result. Actually this is not something spectacular given the variety of IE language family, especially considering that some of the above mentioned pathways are not exactly rare or surprising. They occur very frequently in languages of the world and the situation when two languages follow a multiple similar pathways is more of a statistical inevitability.
Indeed, even though Modern Greek has some limited phonological affinities with Albanian and Bulgarian (which could be explained by Balkansprachbund arguments), it is strikingly phonologically different from Italian, with which it has been rubbing shoulders for millennia. (Yes, there is Italianate prosody in Greek island dialects and Griko, but it appears that, as the Langfocus video amply illustrates, M G has retained fewer tonal features from Ancient Greek than Italian possesses now! Indeed, in an odd reversal of history, modern Greeks marvel at the singsong features of Italian just as the Romans did for A G.) Despite millenia of lexical loans and interactions, it is still terribly easy for Greeks to mispronounce Italian, and vice versa, even though they can learn each other's languages flawlessly. Even Sicilian is decidedly on a different phonological plane.
This, then, might well amount to a tweak of the question above, or a subquestion even, as I am not expert enough to call it a conjecture: A dimension of similarity worth exploring is that M G was heavily influenced by Egyptian/Coptic in its transition from A G, while Spanish was influenced by N African phonologies. To my mind, see below, it might be interesting to contrast Spanish dialects which are more and less influenced by Arabic and Moorish dialects, in hope of discerning patterns. The dramatic shift in Greek phonology is well attested in Hellenistic Egyptian papyri, and their telltale spelling mistakes (Menardos).
My special focus point/question is the following.
Both Spanish and Greek have a fair amount of ambiguity/latitude in the consonant pairs b/β; g/ɣ; and d/ð . G has transitioned to the second variant from Ancient to Modern (with a few notable exceptions, when these consonants are preceded by n or m: so, Modern G has retained (exceptionally) ancient values in anDras, enDeka, komBos, emBaino, synGenes, etc, in fast, informal speech; it is a rule); while S is still right in the middle of the transition--even though I am unsure about its time scale and spread.
I should welcome insights and systematics in pronouncing Spanish, or even discerning the difference in Cordova/Cordoba, Habana/Havana, aɣua/agua, arredondo/arreðondo, viða, across S dialects. Are there well-known trends, and, if so, do they correlate with Moorish influence? (Again, the phonological contrasts to Portuguese, or Sicilian, for instance, are striking. Conversely, I am humbled by also noting the transition in French cheval, though.)
Just flew via Athens and passed the time thinking about this question. Warning in advance that phon* is not my strength, Greek is not my strength and my mobile keyboard doesn't have IPA chars.
First we should ask: are Greek and Spanish phonology actually that similar, and in what ways?
poor in vowels - This shared by most major Mediterranean languages, including Semitic ones, but not Turkish.
poor in consonants - They are both fairly limited, not just in terms of inventories but in terms of contrasts and permissibility in certain positions.
θ like Greek theta or Spanish ç - Besides peripheral languages like Arabic, English and Icelandic, it's possible only Greek, Spanish and Albanian have this.
Probably something with rhythm and stress and timing. Actually this usually affects how a language or person sounds more than sound inventory does.
But if we break those down there are major differences, at least if we ignore recent loanwords:
Greek doesn't allow ch, Spanish has lots of it.
Spanish doesn't allow initial ts or ps or ks, Greek has lots of it.
Spanish doesn't allow initial st, sp, sm..., Greek has lots of it.
Spanish doesn't have words that end in unstressed i or u, Greek has many.
Spanish doesn't contrast s and z, Greek does.
In a sprachbund (or phylogenetic relation) situation we would expect the effect to be not limited to sound inventory, but for the notable sounds to be in corresponding positions in corresponding words.
The many cognates of various vintages show clearly that the rarer sounds that happen to be shared arose in very different ways, as they occur in different positions.
Barθelona vs Varseloni
Xuan vs Yannis
xeke vs seixis
bivlioteka vs vivliothiki
θiklo vs kiklos
θoloxiko vs zooloʝikos
galaɣsja vs ɣalaksias
Modern Greek orthography compensates for its limitations with curious digraphs - hence Ampou Ntampi and Nzini Novgkoront - essentially introducing some contrasts.
We would also expect similarities in other areas, like grammar.
There is some sort of Mediterranean and Greco-Roman sprachbund. Coasts had continued contact with each other for thousands of years. So expected similarity between all language pair there is higher than random.
Spanish is the Mediterranean and Greco-Roman language best known worldwide and in the Anglosphere right now. So we hear "Greek sounds like Spanish" more than "Spanish sounds like Greek".
Italian sounds just as much like Greek as Spanish does. We could measure this, with a list of features, or for example with a spoken language identification machine learning model, or testing humans.
Perceived similarity is influenced by the languages we know. For example, English speakers can't say x or gh and therefore can't contrast them and therefore if one language has one and one the other they sound the same.