What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?
Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic_regulator 

Interestingly, the problem remains easy when additive Gaussian noise disturbes the system and your observations of it: 

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic%E2%80%93Gaussian_control

However, the problem becomes hard as soon as the noise is non-Gaussian (or even multiplicative Gaussian).