Full Disclosure: I am an author of the WPAdverts Classifieds Plugin for WordPress, but i will do my best to objectively explain differences between classifieds themes and plugins and what to look for when building a website for a client.
When thinking of building a classifieds website on top of WordPress you need to first decide if you want to use a classifieds theme or a plugin.
What is the difference between classifieds theme and a classifieds plugin?
The theme is a one-stop solution. You install it on-site and it will always look perfect as the classifieds section design is optimized for the theme. The only thing you need to do is configure the theme from wp-admin panel.
The downside of using a theme is that you are locked in with the theme, you cannot switch to a different one as this will remove your classifieds section (which is built-into your current theme and moving it to a different theme might be complicated).
The best solution to switch to a different design would be to create a child theme for your current theme, this will, of course, require some custom programming knowledge.
Classifieds plugin, on the other hand, will allow you to choose any theme you want, but the design will never be as seamless as when using a theme, you can also find some design glitches (conflicts between theme and plugin) as it's not really possible to have the design compatible with every available theme.
Theme vs Plugin - which one to choose?
Both a plugin and a theme have its place. I would recommend using a theme if you found one which matches your needs for the most part and you will not want to change the design anytime soon.
If you have an existing site to which you would like to add a classifieds section then a plugin is your only choice as switching a theme might not be possible (for example if the client has some theme in mind already).
I would also recommend a plugin if your website will be more than just a classifieds website, that is if you will want to have a blog and pages as the classifieds themes rarely put much focus on the blog/pages aspect of the site.
A lot of classifieds themes you can find on ThemeForest https://themeforest.net/category/wordpress?term=classified the plugins you can find at WordPress.org (just search the plugins section for "classifieds" or "business directory"). The cool thing about plugins at WP.org is that their base version is free so you can test if the plugin will play nice with your selected theme or not.
What to look for in your theme/plugin?
Once you select if you want to have a theme or plugin I would recommend checking the following, especially since you are working on a client project and clients often change their minds :).
Is the plugin/theme easily extensible, that is if it is using actions and filters which allow modifying behavior without modifying the source code. Modifying the source code is the last thing you want to do since you will need to either stop updating the plugin or have the custom changes overwritten on update.
Does the theme/plugin have active support? Quite a lot of our customers are building websites for their clients and sooner or later the client has a request for which the developer needs a tech support advice or help.
Is it easy to customize the Create Classified form this is something the customers pretty much always want to do. Ideally, the solution you select should have some kind of Custom Fields editor.
That's pretty much it from the top of my head :). If you have any additional questions feel free to ask.