Actually, it's just that "c" means not only "with", but also "from" or "off". And the typical antonym for it is "на", when it comes to a direction. For example, "Кот прыгает на диван" - The cat is jumping on the sofa, "Кот прыгает с дивана" - The cat is jumping off the sofa. As you noticed, "c" is confusing, being the general translation of "with" that means joining things together, but for this reason russian has cases. So, using the instrumental case makes it a weird picture of a horse and a bridge jumping together, but using the genitive you get exactly the right sense:)
"Над мостом прыгает лошадь" and "Лошадь прыгает над мостом" are grammatically correct, but it's not the general way to say it. It's better to say "Лошадь прыгает через мост". Actually, "над" implies an action above something, whereas "через" is more about overcoming an obstacle. The last one means there're something like a lift-off and a landing.