We spoke on the phone for the first time.
We spoke for the first time on the phone.
There a multiple ambiguities here.
First, "we spoke on the phone" has two meanings: (1) we had a conversation with each other by means of a phone line and (2) we individually made use of the speech function of one or more phones for an unspecified purpose, for example, we could have used the same phone to talk to a third party on another phone. Given real world knowledge, the first meaning is more likely for the sentences in question.
Using meaning number (1) above, the sentences could still represent four different pragmatic meanings as show below, depending upon order and intonation.
(We spóke on the phóne(,)) (for the fírst tíme).
Spoken with two separate phrases and stress on both "phone" and "first time," the sentence would tend to mean: "We spoke on the phone, and it happened to be the first time we spoke."
(We spóke on the phone for the fírst tíme).
If we remove the stress from "phone," the sentence implies that "phone" is within the semantic scope of "first time." The sentence would tend to mean: "That was the first time we spoke with each other, and it happened to be by phone."
(We spóke for the fírst tíme(,)) (on the phóne).
Spoken with two separate phrases and stress on both "first time" and "phone," the sentence would tend to mean: "That was the first time we spoke with each other, and it was by phone."
(We spóke for the first time on the phóne).
If we remove the stresses from "first time," the semantics of the word "phone" would scope over "first time." The sentence would tend to mean: "It was the first time we used the phone to speak with each other."
The options with the two sets of parentheses are probably disfavored in good writing, since they require an unexpected stress pattern. To use them, you might even wish to add commas before the final phrase.