You got the grammar almost right, however, there are two different cases of einen usage:
- Die meisten Menschen, die Dialekt sprechen, haben erlebt: Der neue Partner hörte einen zum ersten Mal Dialekt sprechen.
- Der neue Partner hörte zum allerersten Mal einen (~jemanden) Dialekt sprechen.
The meaning of einen in (1) is different from (2): instead of meaning any person/any dialect, it refers to allermeiste Menschen, die... from the first sentence and their specific dialect.
So it doesn't mean that the new partner for the first time hears an arbitrary person speaking some dialect (which is virtually impossible living in the D/A/CH area), but that the new partner hears his/her partner speaking his/her dialect for the first time (with people from his/her childhood). Einen can be the accusative of man, but in this case a previously specified man. So in English it would read:
Most people who learned a dialect before Standard German may have experienced a situation like this: [...] an old friend called and their partner heard them for the very first time speaking in [their] dialect.
Der neue Partner hörte zum allerersten Mal einen Dialekt sprechen.
is possible and common for case (2) mentioned above, but uncommon in the context of (1) because einen is a personal pronoun here. Compare the standard word order of:
Der neue Partner hörte ihn zum allerersten Mal Dialekt sprechen.
The original word order is also less ambiguous: in hörte einen Dialekt sprechen, the word einen could be the article of Dialekt, while in hörte einen zum allerersten Mal Dialekt sprechen it is clear that einen is the direct object.
(I'm not sure if you were arguing that hörte zum ersten Mal makes more sense than zum ersten Mal Dialekt sprechen, but in both cases zum ersten Mal can refer to hörte rather than to Dialekt sprechen.)
Maybe the appearence of einen apart from a noun is somewhat unusual for DaF speakers, but I can assure you it's perfectly fine because you can think of it as a pronoun like ihn, sie, es etc.