It is possible to set up a location-based directory using WordPress – I did it recently, and I personally find it easier to achieve than – well, almost anything with Drupal but that’s likely because I have no experience with Drupal.
The trick is to work out beforehand what is best expressed as a taxonomy and what as a meta field, as querying posts by taxonomy is simple whereas querying by custom fields can get very complex and expensive on database resources due to the EAV structure of the postmeta table.
Not sure what you mean by creating page templates – any custom post types without templates fall back to built-in templates as described in the template hierarchy section of the Codex – I believe the assumption is that if you’re looking for your template to be different to the built-in archive, single or index templates you might as well create them from scratch.
tl;dr version: It’s possible, but would take some custom code. Can be implemented either as a plugin or in a theme – I assume your objection to a theme would be that you want the functionality to be unaffected if the client were to change theme?