Probability Theory: The Logic of Science by Edwin Jaynes is, I think, one of the best texts on how to really understand probability.

After reading it, I don't agree with most of your description of probability as as-mysterious-as-you-state, but I do agree that it's easy to find things super weird if you don't look from the especially enlightening angle that Jaynes shows off.