This talk will have three parts. First, I'll give a self-contained quick-and-dirty introduction to the phenomenology of ultra-high energy cosmic rays, focusing especially on the GZK bound and its possible violation. Second, I'll describe my work with Jonathan Feng, Peter Fisher, and Terri Yu, where we analyze a new and apparently very promising way to observe ultra-high energy neutrinos. Finally, I'll describe some new ideas about semi-stable particles, which could plausibly arise in connection with low-energy supersymmetry, stimulated by the GZK puzzle.