I think I have an idea that combines a few of the things people have mentioned. I think I'll go with a wondrous item, and make it plot significant. Lets say it's a religious artifact that either belonged to the orks, or that the orks stole. Local merchants can't afford it, several people want it, and it's still going to be a while before monsters that even could turn the players to stone show up. So now the players have choices to make that will make friends or enemies of several groups in the region.
Thanks for the suggestions. Even if I didn't incorporate them into this solution I'm sure I'll find use for them in the future ;)
And if anyone wants to run this themselves, that's awesome. If it helps, I got a lot of inspiration from the poem "Ozymandias", in fact that's what I'm naming the villain.