The first time I saw a picture of Andrew Robinson without Cardassian makeup, I very nearly didn't recognise him. It's much easier to make out in that picture, although I'm still not sure if I would have known who he was right away if I'd come across him suddenly like that.
My girlfriend and I saw Enrico Colantoni at the Philadelphia airport a couple years ago (he played the dad in Veronica Mars, and one of the aliens in Galaxy Quest). We didn't say anything, since it would have been awkwardly weird to do so, particularly as it would have involved interrupting a lengthy conversation he was having with a friend, but we couldn't help staring a bit.
I like to think that meeting someone of whom I'm a big fan would result in me remaining calm and collected and making some sort of intelligent remark, but more likely I'd just not say very much, with some possibility of coming out with inane babble. I've never actually gone to any sort of convention for these things, but I have on occasion wondered what it would be like to meet Summer Glau and what I'd want to say if that happened. ;) Given that she always has the exact same facial expression in every photo with fans, it's hard to tell what she really thinks of them; if her appearance on The Big Bang Theory is anything like real life, she seems to have a surprising amount of patience. lol