I agree with DRW that finding one that is comfortable is the biggest thing.
Wallin's in San Carlos (same mall as the REI) always has a couple pairs of long fins you ca try on. Make sure you go on a day that David Laird is working there. He is the Freediving/spearfishing specialist.
Though my favourite starter fin or general purpose fin is a Cressi 3000. HF you have strong legs and want acceleration. Or the LD if you like more surface swimming and and go fast with a long elegant kick. One of the nice things about these fins are the extra soft foot pockets which are comfortable on a wider variety of people.
Leisure Pro has 30 day return policy for things of the wrong size. So you can do it that way.
If you are diving Monterey, Sonoma, Mendocino and you are not me. You will probably want to try and get 5mm booties. (I hate my 7mm ones, they make all fins uncomfortable for me) You need to try the fin on with the socks, because they make a big difference on how well it sits.
Check out the
Official Fin Sizing thread.
I have a female diver friend in Marina (near Monterey) Who has a pair of Cressi 3000 LDs size 8/9 which I think she wears with 3mm socks. I think she is a (8-9 US women's).
Any Full foot fin is going to feel a lot more solid that an a loose heel strap fin in the water.