I agree that the "best" plot doesn't exist independent of dataset, readership and purpose. For two measured variables, scatter plots are arguably the design that leaves all others in its wake, except for specific purposes, but no such market leader is evident for categorical data.
My aim here is just to mention a simple method, often re-discovered or re-invented, but nevertheless also often overlooked even in monographs or textbooks covering statistical graphics.
Example first, covering the same data as posted by xan:
If a name is wanted, as it often is, this is a twoway barchart (in this case). I will not catalogue other terms here, except that multiple barchart is one common alternative with similar flavour. (My small objection to "multiple barchart" is that "multiple" does not rule out the very common stacked or side-by-side bar charts, whereas "twoway" to me more clearly implies a row and column layout, although in turn it may take examples to make that clear.)
Pluses and minuses for this kind of plot are also simple, but I will spell some out. As I am fond of this design (which goes back at least to the 1930s), others may want to add sharper criticisms.
+1. The idea is easily understood, even by non-technical groups. Bar heights or bar lengths encode frequencies in this example. In other examples, they could encode percents calculated any way you like, residuals, etc.
+2. The row-and-column structure matches that of a table. You can add numerical values too. Very small amounts and even implicit zeros are clearly evident, which is not always the case with other designs (e.g. stacked bar charts, mosaic plots). Row and column labelling is usually more efficient than adding a key or legend, with the mental "back and forth" that that requires. Thus this design hybridizes graph and table ideas, which seemingly troubles some readers; conversely, I would argue that strong distinctions between Figures and Tables are just historical hang-overs, obsolete now that researchers can prepare their own documents and do not have to rely on designers, compositors and printers.
+3. Extensions to three-way and higher designs are easy in principle. Put two or more variables as composite variables on either or both axes, or give an array of such plots. Naturally, the more complicated the design, the more complicated the interpretation.
+4. The design clearly allows ordinal variables on either axis. Order can be expressed (e.g.) by appropriate shading as well as the order of categories on that axis. Category order on axes can be determined by their meaning, or better determined by frequencies; alphabetical order according to text labels may be a default, but should never be the only choice considered.
-1. By being general in design the plot can be less efficient in showing certain kinds of relationships. In particular, a mosaic plot can make departures from independence very clear. Conversely, when relationships between categorical variables are complicated or unclear, then typically no graph is good at showing more than that weak fact.
-2. In some ways the design is inefficient in use of space by leaving room for every cross-combination regardless of whether or how frequently it occurs. This is the vice of the same principle considered as a virtue. The particular design above spaces categories equally regardless of their frequency; sacrificing that often sacrifices readable marginal labels, which I value very highly. In this example, the text labels happen all to be very short, but that is far from typical.
Note: xan's data appear just to be invented, so I won't try an interpretation any more than is attempted in other answers. But some homespun wisdom deserves the last word here: the best design for you is one that best conveys to you and your readers the structure of some real data that you care about.
Other examples include
How can you visualize the relationship between 3 categorical variables?
Graph for relationship between two ordinal variables
EDIT The general idea, and a Stata implementation, are now written up in this paper.