cache keys $cid naming practices (cache_set and cache_get)
is ':' the recommended delimiter? I haven't heard that : is recommended over anything else, but since it's definitely used all over core, it would make a lot of sense. All cache backends that work with Drupal will be handling : well.
should the module name go first? (seems sensible)?
Yes, this is general practice, not just cache keys.
are there characters to avoid?
None that I've heard of. In general, in 2013, if any system doesn't properly handle any character in a string properly, I would find really bad to be honest. With that said, we'll always be dealing with one form or another of legacy software. So stick to a-z, numbers and : if you're feeling risk averse.
are there other considerations?
Can't immediately think of any.