After working on them for a long time, and then procrastinating for at least as long on wrapping them up into releasable shape, I'm sort of proud to announce my plugins for Quod Libet, (the best music player I have yet found):http://code.google.com/p/thisfred-quodlibet-plugins/downloads/list
There are three plugins in there, in order of increasing complexity and interest:
Very simple plugin, searches for the title of the current song in your library: Good for getting rid of duplicates, and finding possible covers.
Useful only if you have a last.fm account and make use of tags there. This will synchronize last.fm tags both ways, saving them in a custom 'tag' id3 field in your local files. Since Quod Libet has a great id3 editing interface (Ex Falso, also usable as a stand alone application,) this makes adding and editing tags to songs, artists and albums on last.fm much easier.
This gets similar tracks to the ones you play from last.fm and puts them in the queue. It is smart enough not to play the same artists/songs for a configurable time, and has some other options (for instance it can also look up similar songs based on the tags created by the lastfmtagger.py mentioned above.) It works pretty well in creating a consistent yet not wholly predictable listening experience if you have a large and diverse library.
As always, feedback is very welcome, I'm sure there are some bugs left in there, or at the very least some rough edges.
(edit: of course within minutes of posting this I find out last.fm's 2.0 API has gone official, so it appears that once again there is some work to do :) Apparently there's no API for getting similar tracks anymore though. That's a shame...)