I like your ideas on classifying types of packages. It might help people decide on what are best practices for creating an ecosystem of packages (which is a pretty cool thing in Julia).
I actually split things up further in the Str* packages in the JuliaString org, than what you discuss for Class A.
StrAPI provides the functions (empty), and using ModuleInterfaceTools sets up the API in a way that other packages can easily extend the API at different levels (i.e. functions/types that are part of the public API for users, and a development API, needed for packages that wish to build their own extensions) (as you recommend, it has no other dependencies, except for the very small ModuleInterfaceTools).
CharSetEncodings provides the CharSet, Encoding, and CSE (Character Set Encoding) parameterized types, helper functions for working with those types, some basic traits that can be used with them, as well as setting up a small set of predefined CharSet, Encoding, and CSE concrete types (for ASCII, ISO-8859-1, UCS-2 Unicode (16-bit, no surrogates, BMP only), full 32-bit UTF-32 Unicode, as well as validated UTF-8 and UTF-16). This only depends on StrAPI.
ChrBase and StrBase are provide the basic string functionality, but they depend on StrAPI to provide the APIs, and CharSetEncodings to provide the types.
Then there other packages such as StrRegex and StrLiterals add extra functionality to StrBase.
StrLiterals is a class of package that you haven’t really discussed, in that it allows for plug in extensions to it’s behavior. Simply by using an extension package, which can add one or more item to a dictionary from StrLiterals, in it’s __init__ code, you can seamlessly add new format sequences.
StrFormat adds format sequences to handle C printf style formatting, Python-like formatting, as well as a “Julian” form that gets defaults based on the argument type(s), and accepts keyword arguments, all within the string literal.
StrEntities adds in 4 different types of entities, LaTex and Emoji entities, similar to the ones at the Julia REPL, as well as HTML and Unicode entities, in the same way, by adding four handlers to extend the package simply by doing using StrEntities.
In some sense these are like your Class D glue packages, StrLiterals doesn’t have the large depencies, but StrFormat can plug in the code from Format, and StrEntities pulls in the packages and loaded tables from StrTables, Unicode_Entities, LaTeX_Entities, Emoji_Entities, and HTML_Entities.
Edit: now that I see your follow on message, maybe these could be considered class E, because they don’t add any new function names, types, or macros, they simply extend the way their base (in this case StrLiterals) acts.
Finally, Strs is what you refer to as a class C package, it pulls in all the other packages I mentioned above (as well as a nice InternedStrings package, even extending its string literal macro i"..." to handle all of the extensions that are present with StrLiterals, returning a nicely interned Str type string (although that’s kind of a bit more like the idea of your Class D, adding extra functionality from combining different packages).
I’m horrible at naming, but I do think nobody will remember which one is A, B, C, or D.
Here are my ideas:
- Interface packages (like my StrAPI)
- Type/Trait packages (like my CharSetEncodings)
- Base packages (like your Class A, minus the parts I’d put into separate Interface & Type/Trait packages, i.e. my ChrBase & StrBase)
- Extendable packages (like my StrLiterals, your class E?)
- Extension packages (like StrFormat and StrEntities)
- Front-end packages (i.e. your Class B)
- Meta/Environment/Ecosystem packages (your Class C, like my Strs, and DifferentialEquations
- Composite packages (your Class D)
Throw your tomatoes 
at will! 