I run regularly, and I would recommend the Philips SHS8001 earbuds. I have the model with the in-line microphone (SHH8006), but I believe the earbuds are the same on both models. They have an over-the-ear hook that helps keep them in place when sweat begins to make your ears slippery - gross image, I know, but that's what happens. They come standard with 3 sizes of rubber cushions, easy to switch. Find the right size for your ear canal, and the combination of the over-ear hooks and the friction of the rubber inserts should keep them securely in your ears. You can find them online for between $20 and $50 depending on if you buy them through eBay or brand new. They're durable as hell - I sweat on them 3-4 times per week, and I even sent them through the washer and dryer once by accident, still providing decent sound quality for this price range. The attached pic shows them in white, but mine are black, I dunno what other colors they have or if that's important to you.
For a full review I wrote of my headset, (again, that's SHH8006, which has an in-line mic and volume controls), check it out here:
Here's a picture of the earbuds in question: