To people who are interested in sharing to a broad public the essence of their work (actually more of their field) here is what I learned from those experiences.
Proteins are of great help
People know about proteins. As they know about genes. They know it exists and it's important. If the world of proteins is rich, it is also visually attractive. This is one of the only example I found where people could see things moving and not steady pictures. These examples can be protein folding computation or, more appealing, protein-chemical docking. Just tell your audience you can simulate the interaction of a protein and a potential drug and they will think it's cool. Don't forget to also say it is just a screening and that a lot of experimental work will stil be to be done (and was done before).
Simulation of protein-chemical docking, I unfortunately did not find more eye-catching video.
If you have the chance to have some computers around, showing how you can visualize a three-dimensional structure of a protein is always fun. And the structure of some complexes (e.g. ATP Synthase) can be quite illustrative by itself.
Tell how big are the data
People generally realize that biologists now needs computers when you tell them things as simple as "The human genome is made of 3 billions of A, T, G or C". They are totally convinced when you mention a single new-generation sequencing machine can generate in average 10 Gb a day (I don't even mention raw data and these estimates are relatively old). And this is only the raw sequence, annotations of experimentally defined properties highly enrich these data. I like to show the UCSC Genome Browser screenshot below (or live if possible) so that people can have a glimpse at a part of the information we have on the human genome. The region of the human chromosome 21 here represented only count for 0.005% of the complete genome...
If you want to emphasize on the complexity of life you can simply tell about gene interaction networks. Tools such as Cytoscape or STRING can be some great visual allies.
Don't forget the basics
I think it is important to have some appealing images or videos so that people get interested but it is also important not to lie to them. A first thing I like to emphasize is the permanent interaction between bioinformatics approaches and experimental work. Studying a genome or transcriptome is only possible if other scientists established the methods and protocols and generated the data first. It is also important to mention the images presented are some nice chosen examples and that the daily work of a bioinformatician is not always as "sexy" as this. There is nothing more powerful than a basic UNIX shell terminal screenshot to convince non computer scientists...
These are few of the examples I like to use to popularize this broad field which is bioinformatics. I hope it can be helpful to some of you. Don't hesitate to share your tips and examples. =)