It’s important to note that the Phoenicians didn’t self-identify as such, but were simply called that by the Greeks—possibly because they were best known for selling purple-red dye (in Greek, phoinos) which was highly sought after because it was the colour of royalty in ancient Greece.
The Phoenicians weren’t even a united kingdom, as such, but a loose confederation of city states—originally in what is now Lebanon (Tyre, Sidon, Byblos), but eventually including satellite colonies around the Mediterranean, such as Carthage. If you would ask a Phoenician at the time to self-identify, he would have likely said either that he was a Tyrian, or Sidonian, or from some other such city—or simply that he was a Canaanite (Kna’ani—which possibly also denotes “purple-red”, only in Akkadian…)
As such, they spoke Canaanite—much like all other Canaanites: the Moabites, Edomites, Jebusites, and Israelites, etc.. This was certainly the case in the second millennium BCE—during the first millennium BC, these dialects had diverged enough to be considered separate languages, so when the Phoenicians founded Carthage, its name—qart ḥadasht—was already distinct from the Hebrew qiryah ḥadashah. (Likewise, the language of the, for example, from the mid-800s BC, in which the Moabite king boasts of how he had shaken off the yoke of Israelite rule, is already a little difficult for a Hebrew speaker to understand.)
They all used the same Canaanite script, though—which the Greeks (and subsequently, all Europeans, including many modern ones)—referred to as the “Phoenician Script”, thinking that they had invented it, when in fact they hadn’t.