Ability to run many different browsers and tests in parallel. This has allowed us to keep our total test times under 25 minutes (even as we've continually added hundreds more tests and up to 10 browsers) and run tests more often—decreasing the time from bug introduction to detection.
Being able to test mobile devices (iOS, Android, and different browsers on each device) has helped us catch tricky mobile-specific bugs in the past.
We've also found the web-based review features (video playback, step-by-step screenshots, "click to manually take over test", full logs) and API handy for diagnosing failing tests and looking back at the result and timing history.
We also found Sauce Labs to be more flexible than alternatives during the setup phase—if you go just one parallel instance over the limit, for example, I noticed they won't instantly fail your tests like another major provider does, which saved a lot of time and frustration when getting parallel tests set up to start.