It has no random feature, the channels they offer are either hand crafted or based on popularity. The music selection excludes many smaller, and indie, labels. The search functionalities are very limited (the metadata is too low quality).
I wanted to love Spotify, and I really gave it a try. I just couldn't keep using it, all it did for me was to make me angry. In the end it's mostly good for listening to what the major labels think you should listen.
My use case though is that I most often go on Spotify to listen to a specific album I had in mind, either I knew already or heard of it from a friend, blog, local gig, etc. But those times (20% maybe?) I feel like trying something new, I always find something good on Discover.
I wish their UI was better though. The desktop app spawns 7 SpotifyHelper processes that each eat 40mb of RAM and the whole thing feels way slow on my 10ish year laptop. The web app uses flash, and while it consumes less ram, the playback is choppy on my pc. At least the desktop app plays fine once it's started.
This is a pretty solid way to discover new music, but you do need that jumping off point to enable you to say to it 'find me stuff like this'.