I don't know why anyone would flame you for using a santoku. I use one every day of my life as do tens of thousands of the best cooks in the world. I think more of us are likely to flame you for considering a shun. We give you a pass for the cutco and the wolfgang puck since you probably inherited it and because you know they're crap.
in general, I'd avoid shun. their classic line is over priced and very mediocre. Their better lines like elite, premier and edo are good, but overpriced. You can get better for the same or less price.
chefknives to go mentioned in other posts is always a great place to buy. great prices, great reliable people and very good information. There are plenty of other good retailers too, but you can always feel confident at CKTG. if you know what you want, amazon has good prices on a surprisingly wide selection, but you're never going to get any info or any help.
Yes, the first thing is to kind of narrow down the size, but not lock it in Japanese knives are often measured in MM not inches and what is comfortable to an Asian build like me might be a bit shorter than a Caucasian so don't be surprised to see ones that wind up being 6.5 instead of 7 or 5.25 instead of 5. Just consider the ball park.
the next thing is price range. that will determine your next choices like brand, model and type steel.
Also consider handle type.
The next thing I personally do is choose steel. shirogami, aogami, super aogami, vg10. Do you want want stainless or are you willing to keep up the maintenance of a carbon blade?
then I consider reputation, what my friends have and have let me try, etc.
You didn't mention price range, but you did say you were considering shun, so we are just making shotgun recommendations. Being of most income, I am a value for the dollar sort of guy. I will spend to get high quality. I've got more than a few blue, super blue, and powdered metal knives. But it can't be a "money is no object" or "frivolous luxury". I think very highly of the Tojiro senkou line. Mac pros are cheap and easy to maintain. just a quick look at the cktg santoku page show many excellent choices. I see a superaogami for 150 a cheap hammerd Damascus for 120,an R2 for 150 all in your price range
The recommendations that rick allen gave are great. He just turned me on to a new addition to my collection. He didn't mention that takamura to me, which i'll now have to add to my list too. looks pretty good