I know lots of women love the Terry Butterfly. I had one on my mountain bike, but hated it on our tandem. I eventually ended up getting a Brooks leather saddle. I've got that on the tandem and one on my single. They are pricey, but wallingford bikes has (or at least did when I bought mine) a six month return policy, so if it doesn't work out, it can go back.

http://www.wallbike.com/index.php

Veronica