Specialized also makes shims that go under the footbed in the shoe, so those might help with your current shoes. I have to say I'm a fan of Specialized's shoes. I have a typical woman's (narrow) heel, but I need a bit of room in the toebox. I have the Trivents for my road bike and Riata for my commuter.

As to your chamois issues, beware of too much material. I've had issues with chafing with a too-big chamois.