Hi UmmLila --
I don't run but for hiking and walking I generally wear something like this wide-brimmed hat with a tie at the back (I believe I own this particular one):
http://www.zappos.com/p/san-di.....e/product/
It stays on pretty well in the wind, but a bucket-style hat with tie (and less protection) does better for me in those conditions.
Generally I find San Diego Hat Co, Betmar, Scala, and Columbia all have fairly reasonably priced options that get the job done.