I am well aware of
https://iancoleman.io/bip39/ but is there a similar tool that generates ready to print paper wallets with some fancy designs, qr codes, etc)?
There is one open source alternative for iancoleman's website, and I think it also has some advantages because of better QR code design:
https://bitcoiner.guide/seed/What other options are there for a gift where the storage medium is either free or costs cents?
Cheaper than paper?

I don't know about that, but you can always use more durable method with stainless steel washers, they can be found everywhere easily.
Another option is to use encrypted cards like Seedkeeper from Satochip, it's not cheapest method, but it is safer.