Over the last few years, I'd say that my musical taste has expanded quite a bit. I now listen to artists and genres that I probably wouldn't have given a chance before. This is in large part to my Rhapsody subscription. Rhapsody can recommend music in a few different ways:
My Rhapsody - recommends new artists/albums based on previous tracks I've listened to
Instant playlists - creates dynamic playlists
Top artists per genre
New album releases per selected genre
This type of recommendation is certainly valuable. But, it is limited by the fact that you don't have a lot of flexibility in specifying the criteria for how the music should be recommended. In the last year or so I've noticed a number of free services that take the concept of music recommendation and make it much more dynamic and feature-rich. For example:
Visualization - the ability to view a mind/concept map of artists and how they relate to each other
Basic Search - search by artist/genre
Advanced Search - search by musical preference - find new artists and songs by music tempo(slow/fast), mood(uplifting/dark), genre (pop, techno, etc), and era (70's, 80's, 90's)
Social Recommendation - what do other users like?
User Feedback - the ability to flag likes/dislikes about songs. The system will adjust future playlists based on this feedback.
Sample Music - can you listen to a sample?
Update: (01/06/07) I've added a couple more sites based on recent discussions and discoveries. Thanks to Sean Coon for an interesting post on user rating/feedback, and pointing out Pandora. As more sites and services come out, I hope to keep this list up to date.
Musicovery
http://www.musicovery.com/index.php?ct=us
Features: Visualization, Advanced Search, Sample Music

Music Lens
http://www.musiclens.de/contest/
Features: Visualization, Advanced Search, Sample Music

Gnoosic
http://www.gnoosic.com/
Features: Visualization, Basic Search, Social Recommendation

Music Map
http://www.dimvision.com/musicmap/
Features: Visualization, Basic Search

Live Plasma
http://www.liveplasma.com/
Features: Visualization, Basic Search

Last.fm
http://www.last.fm
Features: Basic Search, Social Recommendation, Sample Music

Pandora (Music Genome Project)
http://www.pandora.com/
Features: Basic Search, Social Recommendation, Sample Music, User Feedback

TuneGlue MusicMap
http://audiomap.tuneglue.net/
Features: Basic Search, Visualization
