Alice and Bob - why does it work?

As others have already said, if you want to understand public key crypto, you need to focus on your acumen with module arithmetic ("remainders"), exponents and prime numbers.

Euler's theorem helps to make "the magic happen"

The puzzle pieces DO fit; it's not a concept easily grokked. I have sat at the table for many hours studying and contemplating how it works.

Diffie-Helman is one of the most elegant and useful algorithms every created IMO.

"How Alice and Bob establish a secure line of communication without directly exchanging a password?"

People underestimate how critical DH is to global information technology, as it one of the cornerstones of the SSH protocol's initialization phase, and SSH is the protocol that makes managing remote computers remotely possible in a secure manner.

Few days late but this video is the best explanation I've seen of Diffie-Hellman key exchange:

a reply to: ChaoticOrder

There's also a large number of images/pictures to help with visualizing the algo; here's one with of course, Alice (in Wonderland) and (Sponge) Bob.

In seriousness, if you Google DH exchange and click on the images search results, you'll find some very good pictorial representations. Those sometimes help clarify things.