You want Beets.[1] Anything you could possibly want is doable with the smart playlist feature[2] and the redonkulous power of the queries and metadata (chromaprint/musicbrainz/echonest). There is a plugin for last.fm genres but I have not used it. I am not sure how you got similarities from last.fm but you can definitely use the echonest data to find similar music. There was a good discussion of beets here not so long ago.
[2]: https://beets.readthedocs.org/en/v1.3.5/plugins/smartplaylis...
https://github.com/davidhampgonsalves/beets-plugin-play https://github.com/sampsyo/beets/blob/master/beetsplug/play....
For me, one of the pain points is quality of metadata. It's all very well collecting genres, tags, and similar artists from a service like Last.fm, but you need to be reasonably confident that they align with your own ideas about music. Since everyone's ideas about music are different, this puts you in a tight spot.
Here is their current genre tree: http://rateyourmusic.com/rgenre/ (caution, huge page)
However, they don't have an API, so you would need to scrape web pages to get genres for your albums.
I wrote a simple script which uses Last.fm data to generate a "path" through the artists in my music library based on their similarities. It's very far from perfect, but it suffices to build an album playlist which slowly takes me through several genres. Some day I'll improve it to work based on albums rather than artists.
Ideally, I'd like to be able to run queries on my music library and have an interesting playlist returned to me.