After having used the free Spotify Open intensively for a week now (and occasionally before) I just signedup for Spotify Premium: 7 days free, and now extended to 30 days. That's a nice deal. (BTW I'm in Europe)
I had already found new bands and singer-songwriters via Spotify which I'd never found any other way. Yes, I'll use the iCloud solution and have my MP3 stuff upgraded for that $25 price. But that's my collection and doesn't really invite me to listen to new stuff.
I did like Pandora in the past and Spotify is just better. Even while driving home today, I could continue listening to my Spotify playlist while driving, just by using my iPhone and 3G. Downloading songs so I can listen to them while offline works as a charm as well. Spotify is just easy to use, at first it may look a bit like "where's the music" but as soon as you've found some, you'll keep finding huge numbers of songs you never heared of.
But, I'm not sure if it will be worth the 10 euro per month. Anyway, I have 30 days to decide.