ClassiPress is for classified ads
http://demos.appthemes.com/classipress
Vantage is a business directory
http://demos.appthemes.com/vantage
Vantage specifically is capable of providing some of the features you mention.
Claim a listing? Check!
http://demos.appthemes.com/vantage/listings/good-food/
The "Claim Listing" button is on the same line as "add to favorites".
Ads on home page and category pages? Check!
http://demos.appthemes.com/vantage/
As you can see, there are widgetized ad spots in the header, sidebar, bottom of the listings and the footer.
Premium listing upgrades? Check! Here are a couple of tutorials that describe Vantage pricing plans in detail. You can offer several plans, attach them to categories, offer featured listings and more.
http://docs.appthemes.com/tutorials/...ents-settings/
http://docs.appthemes.com/tutorials/...pricing-plans/
A listing membership is not something that you could do with the theme but there are many possibilities with pricing plans as you can see in the tutorials.
There are maps for individual business listings but not a single map for finding listings. The next major feature release for Vantage will include more map features.
Vantage is definitely the appropriate choice for you.
You can run Vantage and ClassiPress on a WordPress multisite install but they would run almost as separate sites. The only advantage is that users would only need to sign in once to access both sites. If you modified the look of the sites to match, this may give the appearance of a single site.
Let us know if we can provide additional answers.
Cheers!