I find the best way is to do it by degrees.
In my case, I'm never outside without the good old Spyderco Ladybug on my keychain, it's been there for over a decade now. That's the one I let people see first. It's small and has filework on the blade spine, and looks kinda cute.
If all goes well, I graduate them to a Delica sized folder. Not quite a big knife, but certainly bigger than the Ladybug. Interestingly enough, I get very little reaction out of a Delica, while similarly sized Native gets "the look". Probably because it's spear-point and has thumb-rest with teeth on it.
From there on out, big boys can come into play, such as Police and Military. Police seems to work better. For one, the word "Police" clearly stamped on the blade clashes with the "Good lord, that's a murder weapon!" line of thought. And some people, after they see what a Police can do to a cardboard box, they want to try it themselves.
Oddly enough, serrations seem to play a big part in this. I don't know if it's because of the stuff on TV, like Law and Order or CSI or what have you, but people tend to have a worse reaction to a serrated blade. I once had a person look at a plain edge Civilian and say "Oh, how cute!" and then a minute later recoil in horror from a serrated Civilian.
As you may have noticed, I'm sticking pretty much to Spyderco knives. I find their knives in general are just bursting with raw creativity and there's so much variety. One day I'd be carrying a Delica, and next day a Captain, and just the shape alone provokes enough curiosity for people to come check out. Cricket is another good one to transition from Ladybug to Delica with, just because of its unusual shape and handle that doesn't exactly scream "Weapon!"
Of course this approach doesn't work on everyone. Some people are too blind or just plain pig-headed to see common sense.