I voted for the Noblet because it is the most universal, and the deck used for this project will be travelling the globe, used by both men and women.
"Songs" is a cute deck but it's very much a niche, specialty deck - and as someone who owns it and has examined it quite thoroughly, I can tell you - it's a women's deck. It's overwhelmingly female. It's also round. It's also a bit off the wall. It's also a bit of a departure from "tarot." It's also a VERY DIFFICULT deck to use and handle, because the cards are HUGE.
My second choice would be for the Robin Wood. It's a very solid, traditional deck that I think would have widespread appeal to both men and women. It's also easy to shuffle and handle. It's also inexpensive - so if something went wrong in the mail and the deck was lost, it's perhaps less of a financial blow to the donor than the loss of a Noblet or Songs would be.