The fit is so important with climbing shoes that it doesn't really make them ideal presents, so I think probably the best thing in this scenario would be a voucher, or an offer to go shopping for them later. Otherwise try to buy them somewhere local so if they don't fit she can go in and try other sizes on and find the right pair.
The best place to start is probably cheaper beginner-friendly shoes like the La Sportiva Tarantula or Tarantulace (the difference between these is velcro vs laces), and as climbing shoes are generally worn in a smaller size, I'd suggest maybe one full size smaller than her everyday shoes.
Whether she climbs with ropes or without (bouldering), and whether she intends to climb mainly indoors or outdoors could be important distinctions, because some shoes are designed with a particular kind of climbing in mind. The bouldering shoes are usually velcro and a bit more uncomfortable, with the assumption being you can take them off between climbs. Shoes for roped climbing usually have laces.
Depending on your budget I personally would recommend the La Sportiva Mythos. They're a classic shoe that have existed for years and are good for rope climbing outdoors, but I personally find them the most comfortable shoe I've tried and wear them bouldering all the time. They stretch with time and are sized quite big, so while my everyday shoes are size EU38/UK5, my Mythos are EU35/UK2.5 so I'd suggest maybe trying these two sizes smaller to begin with. But fit is also dependent on things like foot shape so it's hard to compare with others' experiences!
If it doesn't ruin the surprise, I'd be tempted to ask her to go try some on and report back with what fits. Otherwise if she has specified a size, you could try phoning up her local climbing wall, finding out what brand their hire shoes are, and getting her a pair of those in the right size since you know that's something she's tried and works.