I found a cover for my Magic at Fommy.com who shipped it to Canada fairly cheaply.
I bought their rubberized black one for $13US. It's cheap, feels good in the hands, but difficult to remove.
I also picked up an HTC branded 3.5mm adapter so I could use any set of headphones I wanted.
http://www.fommy.com/
-Rod