Is there a difference between a store and a microstore?  If so, how do I create a new store?

Here's what I thought:

storefront - complete new deployment, implementation of an americommerce site
store - same deployment, each site could have it's own style, theme, domain, etc, but they would mostly share the same product catalog.
microstore - same deployment, same theme, different pricing structure for each microstore, different target audience

However, I can't seem to find where to add a new store.

That's pretty close, we'd call the second item a Multistore or Multiple Storefront.  You have to contact sales or your account manager to create a new Multiple Storefront as these are manually provisioned by our systems operations department to the appropriate resources.