Multi-level business directory?

Hey, I’ve got what I think is a real challenge here. A friend of mine asked me to have a look at a rather old site whose primary strong point is that it works as a directory for a fairly large number of local businesses and organizations. I’ve been looking seriously into migrating to WP, and the main stumbling block is whether it will be possible to implement a comparable directory in the new system.

I’ve been looking through a number of cool plug-ins in this category, but I think I have a requirement or two that might make things more complicated:
It is organized in several layers, depending on how much a user wishes to invest in their presence on the site and with the organization behind the site (essentially, it’s all about horses, if anyone was curious). So first you register as a user, then you choose from a few different categories, all of which affords different levels of service – from a few lines of text and a small picture to large logo and longer description. Once you’ve choosen your preferred level, you also choose what category – business, club and so on – you feel you belong to, after which you get sorted under that heading on the site.

So yea, it’s the multiple layers and categories I’m a bit hesitant about. Anyone who has any thoughts or experience, or maybe even a good plug-in, to share on this?

Many thanks in advance for any input!