Well, I followed Bob's advice (and incredible PM help) and bought the Sennheiser 250s. They are pretty much exactly what I was looking for. I'll try them on my first flight in about 2 hours, but on the train here they were great and I even managed to sleep for an hour which I almost never do, though the music ended way earlier than that. Comfortwise, they are really different from what I'm used to. I'm used to foam ear pieces, for example. That said, I'd say that they are quite comfortable. I definitely don't find them too tight, for example.
The main thing that worried me was the battery case. I really think that this could be implemented better. It really is big. Fortunately the wires are really long, so it fits right beside my iPod in my pocket. I could never run with it, though. (Yes, I don't need or want NR when I run, but I do run when I travel, so may have to bring 2 headphones). So overall, it doesn't bother me as much as I thought it would. We'll see how things go over the next few travel-filled weeks.
Thanks,
Dr. PITUK