Question: To me, "over easy" seems to refer to the pan, because I think of a pan sitting atop an easy flame. "Over hard" makes me think it refers to the egg, because the liquid becomes solid. Then again, maybe it's something else altogether.

Answer: 
I'm pretty sure that "over hard" came first: it's [diner jargon](http://en.wikipedia.org/wiki/Diner_lingo) that the eggs should be flipped **over** and cooked until they are **hard**. Now if you want it flipped but not hard, well the opposite of hard is **easy**, right? (Sure, you could say soft or runny, but diner slang is often supposed to be funny, a bit of an in-joke, and opaque.)
Most likely, *easy* refers to going easy on the temperature and duration, and hard on the condition of the egg, as you suspect. We can play hard and work hard, but we don't really speak about cooking hard. The egg yolk gets solidifies atop even an easy flame, given enough time. And of course, *easy* doesn't refer to the liquid condition of the yolk.