I wish GoG would do gift certificate. That would be so sweet.

To me, this is the best idea. You could use some of the artwork related to the game, and add your own personal touch to it (gift message, game code, etc). The disc would serve an additional purpose as well, allowing the receiver to have a physical medium to back their game up on and keep as long as they want.