As a NYer I encounter celebs with some frequency but of course am too cool to interact with them. (Also figure they probably get bothered enough during the course of their day.) The exception is if I don't see the person coming--if they appear right in front of me, out of nowhere--when I'm startled and have a tendency to say something lame like "I admire your work, sir." Wallace Shawn and Chris Noth have been among the "beneficiaries" of that.
Randomly saw Whoopi Goldberg crossing a street in Soho--gave me a really pleasant smile. Passed Harrison Ford walking on the sidewalk in Midtown--he realized I recognized him and just gave a little shrug, sort of rueful. (He's full grown, but not as big a guy as I'd thought.)
And Sarah Jessica Parker in the supermarket. (They live in the neighborhood.) This was a good while back and she was probably around 40. A small person and *much* better looking than any photo I'd seen of her--basically makeup-less and just looked like someone's youngish mom. Didn't say anything to her, of course, but she gave a small smile. Would have been hard not to recognize her: She was on the cover of two magazines at checkout, which I thought was kind of funny.
I'd imagine people in LA have encounters all the time--can't heave a brick out there without hitting some kind of celeb.
Oh, and in '68 I lived in the same building in Flagstaff as Jim Ryun. Was in the elevator with him once or twice but was just a kid and stayed quiet. Probably a relief for him not to have yet another person pestering him--crazy to think how much pressure he was under, and he was only 21 at the time.