My first trip abroad was to Greece and I loved it!. Since then I have traveled to 51 countries and lived in 4 of them (besides the US). My mom was never really interested in travel but one year I took her to Turkey with me and she was just thrilled. She said she would have traveled more when she was younger had she realized what it would be like (I honestly don't know what she was expecting).

One thing that you might want to consider is if you or your wife has information on family history. Some people really go into great detail about that and visit the home cities of their ancestors. Your wife might be more likely to consider foreign travel if she could research her family history and visit the places where her family came from.