Apologies if this is already somewhere in the long list of suggestions...
A top hat struck me the other day as a very useful/flexible item. Yes, LEGO's made one in the past, but it is a little stiff compared to today's designs, and (to the best of my knowledge) it only ever came in black.
Something with a curved brim, a band, maybe slightly more broad than stovepipe. It would work in pretty much any setting from 1850s and on (westerns, Victorian, 1930s, modern, steampunk, etc.), and also in a ton of colors.
Just another random thought.