Offer to take her shopping. You need to try them on. I can wear practically any size 39 cycling shoe I try on, but my boyfriend tried on basically every shoe available in all three local shops (maybe 15 models or so) and only one was comfortable for him.

Also, size is very individual. I wear a 7.5 - 8 street shoe and a size 39 cycling shoe. Judging from what I have read on this board, a lot of women who ostensibly have the same foot size wear a completely different cycling shoe size (lots of 40.5s and 41s, it seems).

Besides, it's a nice romantic gesture .