I think the issue isn't randomness in general, but rather randomness where part of the outcome space is just "you lose" instead of being a different challenge t

I think the issue isn't randomness in general, but rather randomness where part of the outcome space is just "you lose" instead of being a different challenge that you can somehow overcome. Even then, it depends on the overall flow and UX of the game; if it's cheap enough to try again, even a pretty bleak outcome space can become tolerable or even interesting (cf. slot machines).