I've switched back and forth between this and Pandora. I do not have a Spotify account either...
I've had two *major problems with Nokia MixRadio.
1) While connected to WiFi, and have 'offline' turned off, it's played the same order of songs back to back over a period of a few days. For instance on Day 1 it would play song A, B and C. Day 2, without opening it previously, it would start on song A and then play B and C.
2) I started a mix with three bands that it found the cover art for (meaning it should know this bands genre, sound alikes, etc). It will regularly play some weird bands that are no where in the scope of what I'm playing. For instance, I've picked 3 metal bands and regularly hear different Jamaican style bands.
Other than that, I love the fact it's free and you can create your own mix!