Talk to the bike shop about letting you try different saddles. They should let you do that. There are about a zillion types of saddles. Don't settle for something that isn't comfortable. Speaking for myself, I had to try about 6 different kinds. I finally am comfortable on a narrower "mens" saddle because the women's were too wide in the nose and rubbed my legs. Also, the squishiest one may not be the best. They tend to feel too soft on longer rides. You'll have to judge by your own riding style.

One other thought... if your shop won't let you swap saddles, try Terry. They'll let you exchange. You will get stuck with the shipping charges, but it's better than a sore butt.