Whenever I interact with an AI leader (natives, the king, whoever), my game freezes for 15-20 seconds as if my computer is having a stroke trying to display the diplomatic dialogue screen.

Example: I walk next to a native tribe to meet this tribe for the first time. My game instantly freezes about 20 seconds, then finally the leader head pops up introducing himself to me.

When I click to contact the King, it takes 20 seconds for the actual dialogue to appear on-screen. Whenever I click a native tribe leader's name, I have a 20 second freeze before their face pops up.

This glitch is occuring both in single player and multiplayer.

I have a quad core Intel processor, 4 GB of RAM, and an NVIDIA GeForce 9600 GT video card. My computer is better than 95% of systems running this game. What the hell is causing this game-ruining problem?

Try changing this in the ini (its = 0 by default). Despite the description talking about "movies" it will also speed up LH loading.

; Dont show the game background during movies - may speed up movie playing
HideMovieBackground = 1

Why is this glitching on my system though?

Well, this i cant tell you...

It might be not up-to-date graphics or other drivers.
Or stuff running in the BG chewing up ressources (maybe even stuff you are not aware of...)
Then again - some systems are just more picky than others, without any explicable reason.

PS.: Not sure if it is applicable for you, but i remember reading somewhere that on multi-core systems it is better to force the game to use only one core.

I have the same problem with both CIV och Col, it is a movie thing, in CIV i set movie quality to medium and in Col I do as Refar said