The Apple in-ear buds ($39, I believe) are very comfortable, IMHO. I have one pair that I switch back and forth between my nano and my G5 iPod.
I call the ones that come with iPods the "Cardinal Ximenez" earbuds, after the infamous cardinal who ran the Spanish Inquisition. They're that painful.