Available free from here:
http://www.mediamonkey.com/
I'd highly recommend getting the Zune skin as the default skin is so so but the Zune is quite nice. It can be found here:
http://www.mediamonkey.com/wiki/index.p ... and_higher
Someone's making an iTouch mini player as well but here's some examples of the mini Zune:



The full size Media Monkey has a new (optional) iTunes type search, normalizes audio levels, etc.
There's really a ton of features. It's easy to use but you can also get really detailed with it. Very powerful tagging features.
You can see all the things that have been added/fixed since version 2.55:
http://www.mediamonkey.com/sw/whatsnew.txt
From the amount of fixes listed, it's obvious that they spend a lot of time making sure this app works well.
It's very fast updating the database. I only have around 5K songs atm but it indexed them quickly (even the first time) and can deal with 50K songs according to their web site.
This is the mini player iTouch version that should be out in a week or so:

Kinda cool. I like to have some sort of music window up most of the time since I have a second monitor so these are a little more pleasing to the eye than most. There are still task bar modes etc. You can set transparency levels, etc.