Both effectively do the same job, grip a rope as an auto bloc or an ascender.
What are the pros and cons of each?
Why/when would I choose one over the other?
As already stated, these are very similar knots regarding their use. So there is not much that differentiates them from each other, or to other friction hitches. The advantage of the prusik is the "clean" design: All strands are neatly position parallel to themselves, so it is easily inspected for correctness. For the Klemheist this is not the main criterion; there the loop must be on top and short, so that the wrappings below get squeezed tightly when loaded. This is not harder to tie, but certainly harder to inspect. This is mainly an issue in education; for self-checking, simulating a load situation while still secured is anyway the best option. One advantage of the Klemheist is that it can be used with both cords and slings, Prusik only with cords.
Both knots excel at simplicity in design, but have some drawbacks compared to more sophisticated friction hitches. They block very well, but are hard to loosen after load. So they are good for backups, while for ascending a dedicated ascender device or more elaborate knots (the Fritz Bachmann variants of the discussed knots, the Prohaska, ...) are better suited.
So with cords you can choose either depending on personal preference; for slings you use the Klemheist due to necessity.
A prusik works in either direction, which is sometimes important.
For example, if you were traversing using an old, fixed rope rigged horizontally, you could attach a prusik to it from your harness. If the rope were to break (either to the left or the right of you), the prusik would save you. If you were using a klemheist, you would only be safe falling in one direction or the other.
Another example is bailing off a route where you only want to leave behind one bail biner or piece of trad gear. As shown in the right half of the image, a prusik would save you if the top piece of pro were to blow. A klemheist might work too, I'm not sure. If it did work, it would still be easy to accidentally rig it incorrectly since you'd want it to be the opposite way that you'd rig it for ascending or a rappel backup.