Good question and you're lucky, I stumbled across the answer myself just a few days ago and it's a doozy: the preference has nothing to do with Mail at all and even when I tell you how to fix it, you'll say "really? this is the computing system that's supposed to be easy?"

It's a challenge for an interface designers when they want to have a visual consistency across multiple applications. You and I might think of Apple Mail as a standalone app, a tiny world unto itself, but the developers back at Cupertino HQ see it as one of a number of apps that together comprise Lion. To let people change the appearance of a single app breaks the interface consistency. Getting a glimmer of the solution? The change you need to make is actually through System Preferences. Weird.

First, though, let's have a look at what we're talking about. Here's Apple Mail with really big sidebar icons. Bigger than I want, for sure:

To remedy the problem, we're going to have to go completely outside of Mail. From the Apple menu choose "System Preferences" and look for "General" on the top left:

Click on it, then look half-way down at the new setting for Sidebar icons:

There are three choices: small, medium and large. Pick the one you want and within a second, Apple Mail will see the modification and resize its icons:

That's better. Fixed.

Now, why there isn't a redundant setting in Apple Mail and/or the option of having, say, big icons in Mail but small icons in Finder windows, I can't say. So it goes...