Spotify is OK, but unless you are planning on upgrading to Spotify Premium ($9.99 per month) it’s just another music player for your computer, only with limited access to other music. Premium is required for the phone app. It’s kind of like Pandora, but you can actually pick the songs you want to listen to, but not forever. The free service is unlimited for the first six months. There is a 10 hour/month limit after that. You are also limited to 5 plays of any given song per month. I got a code for a free month of premium, and the Android app is pretty nice, but I don’t think I’ll would be willing to pay $10 a month for it.
If you’ve already got a pretty nice music collection Google Music is great. It allows you to upload up to 20,000 songs and access them from anywhere. Especially if you have an Android device, but you can still access your music on iPhone or iPad by navigating to http://music.google.com.