Something along the size of the Shures is as big as I want to go. What have the best fidelity, preferably at a cost that is something less than the price of the iPod itself?
Well from what I hear the Shures are great. I have a pair of Etymotic ER-6i which I love. I have had them now for 8 months and only replaced the filters once.
Both companys offer different earphones with different quality. The more you pay the better the earphones. You can spend a lot of money if you want.
The Etymotic Er-6i and the Shure E2c are great 'phones and won't cost you the earth. I got the Er-6i because they were white (oh I'm so vein) and you don't have to run the cord behind your ear like the Shures. But everyone who has Shures loves 'em.
P.S. I got my Etys from ebay - much cheaper than here in Oz
Panasonic HJE-70's. Great sound, amazingly comfortable, and can be found pretty cheap online (retail for $170 but Amazon consistently carries them for ~$80).