Paper wallet is your best bet. Its free, you need to print it only, but you control the keys.
You can choose design of it, how it looks and its nice looking thing for gift (if you chose right :>)