Here is the problem. In order to achieve a reasonable battery life, many designers limit the ability of the audio output stage to deliver substantial amounts of current. What this means is that the device may sound great with higher impedance headsets but sound restricted or distorted with lower impedance headphones.
I have a pair of Grado headphones which sound absolutely great with my home hi-fi equipment but really suck with an ipod or my XM Inno. Yes, an amplifier would remedy this situation. That's not what I do. I have another pair for use with battery powered devices. It is a Koss Sporta-pro. It's about 60 ohms compared to the Grado 30 ohms. This is enough to make a great difference.
If you gotta have the Grados (or Senheisers), get an amp. Otherwise search the net for something with a little higher impedance.
Good luck & let us know how you do on this. This is a good topic that many need to know about.