I don't use the album browse feature, so can't match based on that. The only music player I know that has an animal in its logo, that remotely appears like what you describe, is gmusicbrowser:
http://gmusicbrowser.org/ (though I guess this is a camel).

Here is a list of other music players for Linux, either their names or logos may ring a bell for you :
http://alternativeto.net/software/quod- ... form=linux. After using Rhythmbox for years, I've recently switched to Quod Libet as Rhythmbox has been broken by the Gnome 3 developers. Quod Libet has an impressive number of plugins, and lots of ways to browse your music (much more, and well organized, features than Rhythmbox). You may like it. Very lightweight to boot

And as nomko shares, the other music players have improved over the years also. Though I can understand your desire to match what you enjoyed in the past.