(decided to write this down to have all this in one place, in a way at least I can understand, I hope it helps others which had the same questions as me when they came across STUN/TURN/ICE acronyms and found it all confusing, not knowing what was needed first and what problems each solved)
NAT devices, basically keep tables that map external IP:PORT to internal IP:PORTs and when IP packets come in and out, they rewrite these packets so that they IP:PORTs are changed (initially with the goal of reusing a limited number of public addresses, but lately to restrict direct communication between machines inside restricted networked environments).
This works fine for certain protocol standards, but it's not so good when you have a custom protocol that carries inside IP:PORT information as the NAT device won't look inside the packet, and in many cases, we don't want anybody looking inside the packet, for instance when the data is encrypted, there