Hello!
GeoDirectory is definitely ‘targeted to a drill down location type of directory.
Once your user chooses a location, as long as they stay on the GD pages, the location will be preserved/remembered and they can click around to see more related pages specific to the location they are interested in.
I think you would be creating unnecessary complexity with 5 CPTs. That choice would probably limit your options in a wide variety of ways down the road. If you are really concerned about being specific with a place, I would lean towards making a site for each state instead of using 5 CPTs on one site.
Categories are really important for SEO, and so are all of the GD options. Instead of adding the work with CPTs, focus on the extra information you can add for SEO using the GD options on categories and locations, using GD fully and completely, with a single place/CPT for the type of listing you have, using categories to differentiate them.
That approach will limit the complexity and keep you focused on high impact details. You can always export the listings and re-import later into a new CPT if you really need to.