Thinking about small sizes I figure that something with an unusual shape, e.g. a silhouette, might even be better. The Linux penguin both has an unusual shape and a strong set of colours (black / white / yellow). I have been thinking about silhouettes of a gnu and a rider last week. There are a few more logo samples at my page:
Being silhouettes, there's an inevitable problem with foreground/background ambiguity, namely that the flowing hair behind the back looks more like caricatured armpit hair. Which may be no less European, granted.
A gnu being the surest way to quick irrelevance notwithstanding (mountain goats are far hardier), the second Europa Riding line art is my favourite. Use without map on web, with faint green map on hard copy. There, sorted.
David