Can I download all tags and the contacts that have those tags?

Sort of.

You can download/export all contacts, and one of the columns you can include is Tag IDs.

Then, separately, you can export the list of tag names and IDs.

From there you should be able to use Excel formulas to get what you’re after!