The only time I've ever gotten a box that was not leatherette and "cheap" was when I bought a diamond pendant on chain which cost approx. $1,500 on Blue Nile. The box that I got was about palm sized and hefty and sturdy. I don't keep boxes (I also throw them out) but I kept that particular one.
Lovely choice in gift, your girlfriend will be very happy!