Adding a module dependency to a public project
I would use hook_requirements() for this, at least in your next version.

It takes severity parameter:


  The requirement's result/severity level, one of:
  
  
  REQUIREMENT_INFO: For info only.
  REQUIREMENT_OK: The requirement is satisfied.
  REQUIREMENT_WARNING: The requirement failed with a warning.
  REQUIREMENT_ERROR: The requirement failed with an error.
  


What you want seems to be REQUIREMENT_WARNING


  Requirement severity -- Warning condition; proceed but flag warning.


That way admin will see that requirement is not satisfied, but will be able to proceed anyway. I currently have this in one of my projects:



If I click "try again", I can proceed, but I will not be surprised if next version will not allow me to proceed, and I am aware that some important functionality will not work if I will proceed now, without addressing this warning.

It's also a good idea to provide a link to installation instructions or drush installation helper syntax in your warning message, as seen on the screenshot.

It should be a temporary solution only, of course. After a week or two you could move your dependency to .info file. Module users will expect it, informed by your warning, and no further logic or warnings will be needed anymore.

Of course changelog and project's page should be a main source of information about serious changes, but many people update using Drupal's built-in functionality and will not even see module's page before update, so it is unsafe to assume they will know basing only on the assumption you posted it there.