WordPress as a content management system organizes pieces of data into categorizations. It calls any individual piece of data that it might manipulate or display a "post", and any way to classify or organize that piece of data a "taxonomy".
But not every post is the same, and there are often groups of posts that have a distinct set of properties that are stored, interacted with, or presented differently from the other groups. WordPress appropriately calls these groups "post-types". By examining a few of the default post types, we can see what makes them unique:
- Posts of the
page post-type tend to be static, timeless presentations of content. The actual content or display of a page is what is important to convey to end-users, so the author and creation date of a page are often largely ignored. The path to accessing such important content is usually deliberately planned, so pages can be organized hierarchically. Since they are usually directly linked to, there's not much of a reason to categorize them with taxonomies, especially since the content of two pages rarely has any similarities (except of hierarchy). In order to succinctly allude to their content and for the sake of organizational purposes, a title is a very important property for a page.
- Posts of the
post post-type emphasize chronology, authorship, volume, and classification. Anticipating such a large quantity to be created over time, it would be unfeasible to plan deliberate routes to each individual post, and so "archives" are used to organize posts by certain criteria (by default, reverse chronology). Displaying all of these items in different layouts as one might for pages would prove difficult (and likely confusing for end-users) so posts are usually displayed in a consistent manner. In order to make it easier to find posts relevant to the end-user, taxonomies such as "Categories" and "Tags" are used to classify posts by what they contain. As with a page, a post's title succinctly alludes to it's content, and when a post is linked to from an external site it is very important; within the CMS itself, a post's title is arguably of less importance than a page's, as the post's content can be located through other means.
- Posts of the
nav_menu_item post-type are little more than links with titles. Their authorship, their chronology, and their classification are all irrelevant. In fact, they're not even directly displayed to end-users; only when a WordPress navigation menu explicitly references them in order to provide a means to navigate between content and URLs are they really useful to visitors.
It would be unreasonable to try and describe these different types of data using the same properties - and displaying them all using the same template would probably be little better than staring at database tables. So they are differentiated with post-types, to emphasize what makes them distinct from one another, and to allow them to be displayed and interacted with in a way that makes sense for what they.
From what I understand about your website in question, the pieces of data that you are actually trying to display and organize are "services" - therefore it makes sense that you should create a
service custom post-type. It doesn't sound as though you are interested in organizing and presenting "states" - so it would be unreasonable to create a
state custom post-type, unless you have something special to convey about each individual state. Rather, you wish to organize your
services by states. As mentioned above, the constructs that organize posts in WordPress are "taxonomies" - therefore you would create a
location custom taxonomy and associate it with your
service custom post-type. This will allow end-users to sort your services by location.
Depending on the options you choose while registering your custom taxonomy and post-type as well as your permalink settings, you can end up with a variety of URL structures - in many cases several of these URLs will lead to the same end-point, simultaneously. I have not seen any evidence that such URLs are detrimental to SEO... I'm fairly positive that the Google crawlers do not strictly interpret URL chunks as hierarchical structures, as a large number of applications use them for arguments, or dynamic endpoints - I think the crawlers are little more clever than you give them credit for ;) . Given that WordPress powers 24% of the web, I wouldn't be too concerned about it misinterpreting WordPress's default behavior. You could always submit a sitemap if you want finer-grained control, just to be sure.
There are some edge cases where removing a custom post type's slug from a pretty permalink makes some pragmatic sense, but more often than not it's only done for subjective vanity.