1) For the love of God, introductions are not about you--its about them. You'll get your chance to tell your story if you first make their needs a priority.
2) Always introduce yourself to the person sitting next to you on a plane. You might be surprised by what you learn from them over the course of a 3 hour flight.
(If I ever need a job I'm buying a round trip ticket with a 12 hour layover at IAH. Ruby's bar is like one rolling job interview for the extroverted who likes to travel.)
The corollary to that point is that you have to be able to quickly gauge the level interest of the person sitting next to you. Introduce yourself, then wait and see how the person responds, if he show no interest in talking to you, then don't pester them.