I am looking for a meaningful explanation to Numbers 23:19. What is the significance of God being compared to a "(ish) MAN that lies" and a "(ben adam) SON OF man that relents?"
There is a beautiful lengthy piece from Rav Yaakov Tzvi Mecklenburg in his Haketav Vehakabalah on this verse. In short, although "Ish" and "Adam" both have connotations of being both wicked (במות אדם רשע, איש אשר אין מעצר לרוחו) and righteous (ויקרא את שמם אדם ביום הבראם, משה איש אלהים), there is nonetheless a fundamental difference between them.
The term "Adam" refers to one who has a very base, coarse, and crass nature. As his name testifies, he is one who is very earthly and connected to physicality. The term "Ish" refers to one who has a very refined, sensitive, and nuanced nature. The root of this name is "Yeish-יש" or "there is", representing the truly good and spiritual nature of the world as it is inherent and eternal(ישיות וקיום נצחי).
In our verse, the "Ish" refers to a person who is naturally a trustworthy person and one who calls upon him for a task assumes with certainty that he will execute it. Yet ultimately he is just a man, and something outside of himself can be the cause for this task never coming to fruition, even with all of the efforts of the "Ish". The term "ויכזב" in our verse refers to the failure of a given thing, like
לא יכזבו מימיו" - ישעיהו,נח,יא".
"Adam" in our verse refers to a person who is naturally an untrustworthy person who would regret even accepting the task. This is the understanding of "ויתנחם" in our verse.
Bilaam announces that not only is God not like a lowly, untrustworthy, and incapable man, rather he is not even like an upstanding, trustworthy, and capable man. For even a man as lofty as he is a mere mortal and subject to forces beyond him, this is not so with God, as he is the source of everything and subject to nothing.
I highly recommend reading the piece in full.
Rav Hirsch explains that an oracle speaks in parables and and can use terms that can be misinterpreted or have multiple meanings. For example the story of King Midas and the Oracle at Delphi in which the message was A mighty kingdom will be destroyed and King Midas thought he would win while he was actually soundly defeated. Hashem explicitly stated that Bnai Yisrael would be blessed and Bil'am was forbidden to curse them.
As Rav Hirsch explains
לא איש וגו. Immediately on your first request Hashem told me regarding this people כי ברוך הוא that it was blessed. Hashem does not speak in the ambiguous words of the oracles. If Hashem says that something is blessed it it is blessed, and there is not phase of it that is accessible to the reverse. And if Hashem has once said לא תאור את העם ("thou shalt not curse the people") He does not afterwards change His mind and give permission for the opposite.