Here's my simple suggestion: make Android Market gift cards. iTunes gift cards are HUGE sellers and have become a standard gift, especially for people you don't know well.

Someone with an Android Market gift card will be motivated to figure out how to use the market and will get used to the idea of paying for apps. To me, the lack of a gift card shows a lack of commitment to the Market ecosystem.