I think the earlier comment about one of your sources, Pandora, has gone unrecognized. At 64k AAC you're missing ALOT of information cropped in the compression scheme. That's probably making a neutral headphone like the M50 (which you may not have been impressed with anyway) sound worse... They are likely exposing the weaknesses of the extreme compression. That's an issue you will have with any good set of cans (at any price) when listening to Pandora and other Internet streaming music.
I'm actually re-ripping all of my cd's at 256k AAC vbr... with my headphones and amp I can hear the difference between that and 192k mp3 (what I had formerly ripped at).
Also, good, clean, tooth-chipping, bass takes juice... the average iPod, sound card, etc. just doesn't have the power to dig deep and clean. You may want to consider an amp to go with your headphone purchase.
I can't comment on the 'phones suggested as I have never auditioned them, but I think that once you get a pair that have the bottom end you want, and you drive them with a juicy amp, you'll be smiling for days...